Question

Approach: Greedy

Intuition

According to the problem, the cost x of any fruit must appear an even number of times across the two fruit baskets; otherwise, it is impossible to evenly distribute the fruit with cost x between the two baskets. To compute the imbalance in fruit costs between the two baskets, we can use two hash tables, $count_1$ ​and $count_2$, to count the number of times each fruit cost appears in $basket_1$ and $basket_2$, respectively. For a given fruit cost $x$:

If $count_1[x]+count_2[x]$ is odd, we return $−1$ immediately, since balancing is impossible.

If $count_1[x]>count_2​[x]$, then $\frac{count_1[x]−count_2[x]}{2}$ fruits with cost x must be moved from $basket_1$ to $basket_2$, and vice versa.

Following point 2, we enumerate all such costs $x$ and add each to a list called $merge$ with a count equal to the number of excess fruits that need to be exchanged. We then sort merge in increasing order. According to the greedy strategy, we pair the smallest values from the first half of the list with the largest from the second half to minimize the overall exchange cost. For each pair of costs $x_1$ and $x_2$ $(x_1 < x_2)$, there are two possible exchange strategies:

Direct exchange: Swap $x_1$ with $x_2$, with a cost of $x_1$.

Indirect exchange: Both $x_1$ and $x_2$ are exchanged through the minimum fruit cost m across both baskets, with a total cost of $2×m$.

We iterate over the first half of the $merge$ list, and for each element $x$, we accumulate the cost $min(x,2×m)$ into the final result.

Implementation

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        TreeMap<Integer, Integer> freq = new TreeMap<>();
        int m = Integer.MAX_VALUE;
        for (int b1 : basket1) {
            freq.put(b1, freq.getOrDefault(b1, 0) + 1);
            m = Math.min(m, b1);
        }
        for (int b2 : basket2) {
            freq.put(b2, freq.getOrDefault(b2, 0) - 1);
            m = Math.min(m, b2);
        }

        List<Integer> merge = new ArrayList<>();
        for (var entry : freq.entrySet()) {
            int count = entry.getValue();
            if (count % 2 != 0) return -1;
            for (int i = 0; i < Math.abs(count) / 2; i++) {
                merge.add(entry.getKey());
            }
        }

        Collections.sort(merge);
        long res = 0;
        for (int i = 0; i < merge.size() / 2; i++) {
            res += Math.min(2 * m, merge.get(i));
        }
        return res;
    }
}

Timing

NULL

Completixy

Time

$O(nlogn)$, from sorting

Space

$O(n)$