Rearranging Fruits

Hard
1469.

Rearranging Fruits

Rearranging Fruits is a hard coding problem on arrays, hash table and sorting, asked in Amazon, Google and Atlassian interviews.

Two baskets hold n fruits each; basket1[i] and basket2[i] are fruit costs. You want the two baskets to be equal — the same costs with the same multiplicities, in any order.

In one move you pick a fruit from basket1 and a fruit from basket2 and swap them. The move costs min(x, y), where x and y are the costs of the two fruits swapped.

Return the minimum total cost to make the baskets equal, or -1 if it is impossible.

The original allows costs up to 10^9; here costs are at most 10^4 so the answer fits in a 32-bit integer.

Example 1

Input
basket1 = [5,5,1,3], basket2 = [3,1,7,7]
Output
2
Explanation
Swap a 5 for the 1 in basket 2 (cost 1), then swap that 1 for a 7 (cost 1).

Example 2

Input
basket1 = [4,2,2,2], basket2 = [1,4,1,2]
Output
1
Explanation
Swap a 2 from basket 1 with a 1 from basket 2.

Example 3

Input
basket1 = [2,3,4,1], basket2 = [3,2,5,1]
Output
-1
Explanation
There is one 4 and one 5 in total; they cannot be split evenly.

Constraints

  • basket1.length == basket2.length
  • 1 <= basket1.length <= 10^5
  • 1 <= basket1[i], basket2[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} basket1
 * @param {number[]} basket2
 * @return {number}
 */
var minCost = function(basket1, basket2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rearranging Fruits — Solution in Python, Java & C++

Rearranging Fruits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Rearranging Fruits is a hard coding problem on arrays, hash table and sorting, asked in Amazon, Google and Atlassian interviews.

Problem statement

Two baskets hold n fruits each; basket1[i] and basket2[i] are fruit costs. You want the two baskets to be equal — the same costs with the same multiplicities, in any order.

In one move you pick a fruit from basket1 and a fruit from basket2 and swap them. The move costs min(x, y), where x and y are the costs of the two fruits swapped.

Return the minimum total cost to make the baskets equal, or -1 if it is impossible.

The original allows costs up to 10^9; here costs are at most 10^4 so the answer fits in a 32-bit integer.

Example 1

Input: basket1 = [5,5,1,3], basket2 = [3,1,7,7]
Output: 2
Explanation: Swap a 5 for the 1 in basket 2 (cost 1), then swap that 1 for a 7 (cost 1).

Example 2

Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2]
Output: 1
Explanation: Swap a 2 from basket 1 with a 1 from basket 2.

Example 3

Input: basket1 = [2,3,4,1], basket2 = [3,2,5,1]
Output: -1
Explanation: There is one 4 and one 5 in total; they cannot be split evenly.

Constraints

  • basket1.length == basket2.length
  • 1 <= basket1.length <= 10^5
  • 1 <= basket1[i], basket2[i] <= 10^4

Hints for Rearranging Fruits

  1. Hint 1

    Count each cost across both baskets. If some cost appears an odd number of times in total, the answer is -1.

  2. Hint 2

    Each basket must end with half of every cost. List the surplus fruits each basket must give away; the two lists have equal length k.

  3. Hint 3

    Sort all surplus fruits together and pay for the k cheapest. A swap can also go through the globally cheapest fruit twice, so each payment is min(cost, 2 · globalMin).

How to solve Rearranging Fruits

Only the surplus fruits need to move. Each swap moves one surplus fruit from each side, and its price is the smaller of the two — so pair the cheapest surpluses with the most expensive ones. A detour through the cheapest fruit overall (two swaps at globalMin each) can be cheaper than a direct swap.

Approach

  1. Compute diff[v] = count1[v] - count2[v] for every cost v, and globalMin, the smallest cost in either basket.
  2. If any diff[v] is odd, return -1.
  3. Collect |diff[v]| / 2 copies of each v into one list of surplus fruits (from both baskets) and sort it. It has 2k entries.
  4. Sum min(list[i], 2 · globalMin) for i in 0 .. k - 1 and return the total.

Why it works

Each move fixes at most one surplus fruit on each side, so at least k paid moves are needed, and a direct swap costs the cheaper of its two fruits. Pairing the k cheapest surplus fruits with the k most expensive ones makes every paid price one of the k cheapest values, which is the least possible sum. Alternatively a surplus pair can be exchanged by swapping each with the global minimum fruit, costing 2 · globalMin; taking the cheaper option per pair is optimal.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Forgetting the 2 · globalMin detour gives answers that are too large.
  • Pay for only half of the combined surplus list — the other half rides along for free in the same swaps.
  • A negative odd difference is also odd: check diff % 2 != 0, not == 1.

Reference solution

Python

from typing import List
from collections import Counter

def minCost(basket1: List[int], basket2: List[int]) -> int:
    diff = Counter(basket1)
    diff.subtract(Counter(basket2))
    mn = min(min(basket1), min(basket2))
    extra = []
    for v, c in diff.items():
        if c % 2 != 0:
            return -1
        extra.extend([v] * (abs(c) // 2))
    extra.sort()
    return sum(min(x, 2 * mn) for x in extra[:len(extra) // 2])

Java

public static int minCost(int[] basket1, int[] basket2) {
    Map<Integer, Integer> diff = new HashMap<>();
    int mn = Integer.MAX_VALUE;
    for (int i = 0; i < basket1.length; i++) {
        diff.merge(basket1[i], 1, Integer::sum);
        diff.merge(basket2[i], -1, Integer::sum);
        mn = Math.min(mn, Math.min(basket1[i], basket2[i]));
    }
    List<Integer> extra = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : diff.entrySet()) {
        int c = e.getValue();
        if (c % 2 != 0) return -1;
        for (int t = 0; t < Math.abs(c) / 2; t++) extra.add(e.getKey());
    }
    Collections.sort(extra);
    long ans = 0;
    for (int j = 0; j < extra.size() / 2; j++) ans += Math.min(extra.get(j), 2 * mn);
    return (int) ans;
}

C++

int minCost(vector<int>& basket1, vector<int>& basket2) {
    map<int, int> diff;
    int mn = INT_MAX;
    for (size_t i = 0; i < basket1.size(); i++) {
        diff[basket1[i]]++;
        diff[basket2[i]]--;
        mn = min(mn, min(basket1[i], basket2[i]));
    }
    vector<int> extra;
    for (auto& p : diff) {
        if (p.second % 2 != 0) return -1;
        for (int t = 0; t < abs(p.second) / 2; t++) extra.push_back(p.first);
    }
    sort(extra.begin(), extra.end());
    long long ans = 0;
    for (size_t j = 0; j < extra.size() / 2; j++) ans += min(extra[j], 2 * mn);
    return (int)ans;
}

JavaScript

var minCost = function(basket1, basket2) {
    var diff = new Map();
    var mn = Infinity;
    for (var i = 0; i < basket1.length; i++) {
        diff.set(basket1[i], (diff.get(basket1[i]) || 0) + 1);
        diff.set(basket2[i], (diff.get(basket2[i]) || 0) - 1);
        mn = Math.min(mn, basket1[i], basket2[i]);
    }
    var extra = [], bad = false;
    diff.forEach(function(c, v) {
        if (c % 2 !== 0) bad = true;
        for (var t = 0; t < Math.abs(c) / 2; t++) extra.push(v);
    });
    if (bad) return -1;
    extra.sort(function(a, b) { return a - b; });
    var ans = 0;
    for (var j = 0; j < extra.length / 2; j++) ans += Math.min(extra[j], 2 * mn);
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets