Rearranging Fruits

hard greedy hash table sorting

Problem

Two baskets basket1 and basket2 each hold n fruit costs. One operation swaps basket1[i] with basket2[j] at cost min(basket1[i], basket2[j]). The baskets are equal when sorting both produces identical arrays. Return the minimum total cost to make them equal, or -1 if it is impossible.

Inputbasket1 = [4,2,2,2], basket2 = [1,4,1,2]

Output1

Swap basket1[1] = 2 with basket2[0] = 1 at cost min(2, 1) = 1. Both baskets then sort to the same multiset.

basket1 (comma-separated)

basket2 (comma-separated)

def minCost(basket1, basket2):
    count = {}                              # net surplus per value
    for x in basket1:
        count[x] = count.get(x, 0) + 1      # basket1 contributes +1
    for x in basket2:
        count[x] = count.get(x, 0) - 1      # basket2 contributes -1
    lo = min(min(basket1), min(basket2))    # global cheapest fruit
    merge = []
    for v, c in count.items():
        if c % 2 != 0:
            return -1                       # odd total -> impossible
        merge += [v] * (abs(c) // 2)        # half of each surplus moves
    merge.sort()                            # cheapest swaps first
    total = 0
    for i in range(len(merge) // 2):        # pay only the cheaper half
        total += min(merge[i], 2 * lo)      # direct swap or via lo
    return total

function minCost(basket1, basket2) {
  const count = new Map();                       // net surplus per value
  for (const x of basket1) count.set(x, (count.get(x) || 0) + 1);
  for (const x of basket2) count.set(x, (count.get(x) || 0) - 1);
  const lo = Math.min(...basket1, ...basket2);   // global cheapest fruit
  const merge = [];
  for (const [v, c] of count) {
    if (c % 2 !== 0) return -1;                   // odd total -> impossible
    for (let k = 0; k < Math.abs(c) / 2; k++) merge.push(v);
  }
  merge.sort((a, b) => a - b);                    // cheapest swaps first
  let total = 0;
  for (let i = 0; i < merge.length / 2; i++) {    // pay only the cheaper half
    total += Math.min(merge[i], 2 * lo);          // direct swap or via lo
  }
  return total;
}

long minCost(int[] basket1, int[] basket2) {
    Map<Integer, Integer> count = new HashMap<>();   // net surplus per value
    int lo = Integer.MAX_VALUE;
    for (int x : basket1) { count.merge(x, 1, Integer::sum); lo = Math.min(lo, x); }
    for (int x : basket2) { count.merge(x, -1, Integer::sum); lo = Math.min(lo, x); }
    List<Integer> merge = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        int c = e.getValue();
        if (c % 2 != 0) return -1;                   // odd total -> impossible
        for (int k = 0; k < Math.abs(c) / 2; k++) merge.add(e.getKey());
    }
    Collections.sort(merge);                         // cheapest swaps first
    long total = 0;
    for (int i = 0; i < merge.size() / 2; i++)        // pay only the cheaper half
        total += Math.min(merge.get(i), 2L * lo);     // direct swap or via lo
    return total;
}

long long minCost(vector<int>& basket1, vector<int>& basket2) {
    unordered_map<int, int> count;                  // net surplus per value
    int lo = INT_MAX;
    for (int x : basket1) { count[x]++; lo = min(lo, x); }
    for (int x : basket2) { count[x]--; lo = min(lo, x); }
    vector<int> merge;
    for (auto& [v, c] : count) {
        if (c % 2 != 0) return -1;                  // odd total -> impossible
        for (int k = 0; k < abs(c) / 2; k++) merge.push_back(v);
    }
    sort(merge.begin(), merge.end());               // cheapest swaps first
    long long total = 0;
    for (int i = 0; i < (int)merge.size() / 2; i++)  // pay only the cheaper half
        total += min((long long)merge[i], 2LL * lo); // direct swap or via lo
    return total;
}

Explanation

The two baskets can be made equal only if, for every fruit cost, the combined count across both baskets is even — each basket must end with exactly half of every value. We tally a net surplus count[v] by adding +1 for each value seen in basket1 and -1 for each in basket2. If any count[v] is odd, equality is impossible and we return -1.

For every value with a non-zero net count, exactly |count[v]| / 2 copies are excess on one side and must be swapped out. Collect all those excess values into one list merge. Because every swap moves one excess value out of each basket simultaneously, the number of excess items is the same on both sides, so merge has even length and we will perform len(merge) / 2 swaps.

Now the greedy choice. Sort merge ascending. Pairing the two halves so that the cheapest excess items are the ones we directly pay for, the cost of one swap is the smaller of the two items being exchanged. The cheapest half of the sorted list provides those values, so we sum merge[i] for the first len(merge) / 2 indices.

There is one more shortcut. Instead of swapping an expensive item directly, we can route it through the globally cheapest fruit lo: two swaps using lo cost 2 · lo and achieve the same rearrangement. So each paid swap costs min(merge[i], 2 · lo) — whichever is cheaper.

Example: basket1 = [4,2,2,2], basket2 = [1,4,1,2]. Counts give surplus values {2} on one side and {1} on the other, so merge = [1, 2] with lo = 1. One swap, paying min(merge[0], 2·lo) = min(1, 2) = 1. Answer: 1.

Time: O(n log n) Space: O(n)