2561. Rearranging Fruits
Asked at Atlassian
Difficulty
Hard
Time
O(n log n)
Space
O(n)
Pattern
Array
Companies
1
Problem
You are given two baskets of fruit, basket1 and basket2, each holding the same number of fruits. Each fruit has a cost, given as an integer. You want both baskets to hold the same multiset of costs — that is, after sorting each basket, the two sorted lists must be identical.
You may repeat this operation any number of times: pick one fruit from basket1 and one fruit from basket2, and swap them. The cost of that swap is the smaller of the two fruit costs involved. Swaps are independent, so the total cost is the sum of the individual swap costs.
Return the minimum total cost to make the baskets equal, or -1 if it cannot be done at all.
Swap one fruit from each basket
Constraints
- ●
basket1.length == basket2.length - ●
1 <= basket1.length <= 10^5 - ●
1 <= basket1[i], basket2[i] <= 10^9
Examples
basket1 = [4,2,2,2], basket2 = [1,4,1,2]1basket1 = [2,3,4,1], basket2 = [3,2,5,1]-1Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
How to Think About It
Check feasibility first: both baskets must have the same total number of elements, and each fruit value must appear an even number of times across both baskets combined.
Count the frequency of each value across both baskets. Values with odd counts make the problem impossible.
Identify mismatched elements: for each value, find the excess in one basket that needs to be swapped to the other.
Greedy strategy: for each pair of mismatched elements, swap the smaller pair directly if possible. Otherwise, use the globally smallest element as a swap intermediary.
Optimal: O(n log n) time using counting and sorting. The key insight is that you only need to consider the smaller of each mismatched pair or twice the global minimum.
Optimal Approach
First check if a solution is possible: both baskets must have the same length, and every fruit value must have an even total count across both baskets. Count frequencies of each value across both baskets. For each value, compute the excess in basket1 versus basket2 — this gives a list of values that need to be swapped. Split these into two groups: values that need to go from basket1 to basket2, and values that need to go the other way. Sort both lists. The minimum cost is the sum of min(directSwapCost, 2 * globalMin) for each pair, where directSwapCost is the smaller element in each mismatched pair. Use O(n log n) time for sorting.
Collect mismatches, then pair them cheaply
What Trips People Up in Real Interviews
Start by stating the impossibility conditions clearly — this shows you think about edge cases.
Explain the frequency counting approach: if a value appears an odd total number of times, return -1.
Describe the greedy swap strategy: always try to swap the smaller element directly.
Discuss the role of the global minimum element: it serves as a swap intermediary when direct swap is suboptimal.
Walk through an example where the global minimum is needed to reduce total swap cost.
Solution Code
O(n log n) timedef minCost(basket1, basket2):
from collections import Counter
total = Counter(basket1) + Counter(basket2)
for v in total.values():
if v % 2 != 0:
return -1
c1 = Counter(basket1)
c2 = Counter(basket2)
swaps = []
for v in total:
diff = c1.get(v, 0) - c2.get(v, 0)
swaps.extend([v] * abs(diff // 2))
if not swaps:
return 0
swaps.sort()
global_min = min(min(basket1), min(basket2))
result = 0
for i in range(len(swaps) // 2):
result += min(swaps[i], 2 * global_min)
return resultFrequently Asked Questions
What is the Rearranging Fruits problem?
You have two baskets of fruits, basket1 and basket2, each represented as an integer array. You can swap one fruit from basket1 with one fruit from basket2 at a cost equal to the minimum of the two fruit values. The goal is to make both baskets contain the same multiset of fruits (same elements with same frequencies). Return the minimum total cost to achieve this, or return -1 if it is impossible.
How do you solve Rearranging Fruits?
The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Rearranging Fruits?
Rearranging Fruits is asked at Atlassian. It is a hard difficulty problem.
What are common mistakes on Rearranging Fruits?
- Start by stating the impossibility conditions clearly — this shows you think about edge cases.
- Explain the frequency counting approach: if a value appears an odd total number of times, return -1.
- Describe the greedy swap strategy: always try to swap the smaller element directly.
- Discuss the role of the global minimum element: it serves as a swap intermediary when direct swap is suboptimal.
- Walk through an example where the global minimum is needed to reduce total swap cost.