You have two fruit baskets containing n fruits each. You are given two 0-indexed integer arrays basket1 and basket2 representing the cost of fruit in each basket. You want to make both baskets equal. To do so, you can use the following operation as many times as you want:
i and j, and swap the ith fruit of basket1 with the jth fruit of basket2.min(basket1[i],basket2[j]).Two baskets are considered equal if sorting them according to the fruit cost makes them exactly the same baskets.
Return the minimum cost to make both the baskets equal or -1 if impossible.
Example 1:
Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2] Output: 1 Explanation: Swap index 1 of basket1 with index 0 of basket2, which has cost 1. Now basket1 = [4,1,2,2] and basket2 = [2,4,1,2]. Rearranging both the arrays makes them equal.
Example 2:
Input: basket1 = [2,3,4,1], basket2 = [3,2,5,1] Output: -1 Explanation: It can be shown that it is impossible to make both the baskets equal.
Constraints:
basket1.length == basket2.length1 <= basket1.length <= 1051 <= basket1[i],basket2[i] <= 109In #2561 Rearranging Fruits, the goal is to make two baskets identical with the minimum swap cost. The key observation is that both baskets must end up with the same frequency of each fruit. Using a hash table, count occurrences in both baskets and determine which fruits are in excess in each basket. If any fruit has an odd total frequency across both baskets, forming identical baskets is impossible.
After identifying surplus fruits, collect the elements that need to be swapped. A greedy strategy is then applied: sort the surplus lists and compute the minimum cost of pairing swaps. Sometimes it is cheaper to perform a swap indirectly using the globally smallest fruit as an intermediate. Comparing the direct swap cost with 2 * minFruit helps minimize the total cost.
This approach relies on frequency balancing, sorting, and careful cost comparison. The overall complexity is dominated by sorting, resulting in O(n log n) time with O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Greedy with Sorting | O(n log n) | O(n) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Create two frequency maps for both arrays, and find the minimum element among all elements of both arrays.
Check if the sum of frequencies of an element in both arrays is odd, if so return -1
Store the elements that need to be swapped in a vector, and sort it.
Can we reduce swapping cost with the help of minimum element?
Calculate the minimum cost of swapping.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Rearranging Fruits are common in technical interviews because they test hash maps, greedy reasoning, and optimization strategies. Variations of frequency balancing and minimum swap cost problems appear frequently in top company interviews.
A hash table helps track the frequency of each fruit in both baskets. This allows us to quickly determine which fruits are in excess and whether it is possible to balance the baskets.
The optimal approach combines a hash table for frequency counting with a greedy strategy. After identifying surplus fruits in each basket, sorting and pairing swaps while considering the global minimum fruit helps minimize total cost.
The greedy strategy ensures that each swap is performed at the lowest possible cost. By comparing direct swaps with using the globally smallest fruit as an intermediate, we minimize the total swap cost.