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.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Sorting, Greedy
- Asked at: Amazon, Google, Atlassian
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.length1 <= basket1.length <= 10^51 <= basket1[i], basket2[i] <= 10^4
Hints for Rearranging Fruits
Hint 1
Count each cost across both baskets. If some cost appears an odd number of times in total, the answer is
-1.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.Hint 3
Sort all surplus fruits together and pay for the
kcheapest. A swap can also go through the globally cheapest fruit twice, so each payment ismin(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
- Compute
diff[v] = count1[v] - count2[v]for every costv, andglobalMin, the smallest cost in either basket. - If any
diff[v]is odd, return-1. - Collect
|diff[v]| / 2copies of eachvinto one list of surplus fruits (from both baskets) and sort it. It has2kentries. - Sum
min(list[i], 2 · globalMin)foriin0 .. k - 1and 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 · globalMindetour 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