Rearranging Fruits - Solution & Explanation
Problem Statement
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:
- Chose two indices
iandj, and swap theithfruit ofbasket1with thejthfruit ofbasket2. - The cost of the swap is
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] <= 109
Approach Overview
Problem Overview: You are given two baskets of fruits represented as arrays. Each value represents the cost of a fruit. The goal is to make both baskets identical by swapping fruits between them while minimizing the total swap cost. A swap costs the minimum value of the two fruits involved. If it is impossible to balance the baskets, return -1.
Approach 1: Sort and Compare (O(n log n) time, O(n) space)
Start by counting how many times each fruit value appears across both baskets. If any fruit has an odd total frequency, balancing is impossible because swaps always move fruits in pairs. After validation, identify the extra fruits that must move out of each basket. Store these extras in two arrays and sort them.
Traverse the sorted arrays and calculate the cost of pairing mismatched fruits. A key optimization comes from using the globally smallest fruit as an intermediate swap when direct swaps are expensive. For each pair, compute min(direct_swap_cost, 2 * global_min). Sorting ensures you match cheapest elements first, which minimizes the total cost. This approach relies heavily on array manipulation and greedy pairing, commonly seen in array and greedy problems.
Approach 2: Frequency Map Balancing (O(n log n) time, O(n) space)
This approach focuses on balancing counts using a hash map. Build a frequency difference map between the two baskets. Positive values indicate extra fruits in the first basket; negative values indicate extras in the second. Each imbalance must be corrected by swaps.
Expand the imbalance map into a list of required moves. For example, if a fruit appears four extra times, it contributes two swap operations. After collecting all required elements, sort the list and process the smallest half since each swap fixes two elements. Again apply the greedy rule: choose the cheaper option between a direct swap and swapping through the global minimum fruit. Hash-based counting makes imbalance detection straightforward and highlights patterns typical in hash table problems.
Recommended for interviews: The frequency map balancing approach is usually preferred. It demonstrates strong understanding of counting techniques, greedy optimization, and swap cost minimization. Interviewers expect candidates to first detect the feasibility condition (even total frequencies), then reduce the problem to pairing surplus elements efficiently. The sorted greedy pairing step shows awareness of cost optimization patterns often used in hard array problems.
Approach 1: Approach 1: Sort and Compare
This approach involves sorting both baskets and then attempting to swap elements such that both baskets can be made equal. The key is to minimize the cost of swaps using the given operation constraint, min(basket1[i], basket2[j]). By leveraging sorting, we ensure that similar elements are aligned, facilitating minimal swaps.
In this C code, we first sort both baskets. Then, we iterate through the sorted arrays, comparing elements at each index. If equal, we proceed; if not, we calculate the swap cost using the sorted property. If elements are irreconcilable, we return -1.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we sort in-place.
Approach 2: Approach 2: Frequency Map Balancing
This approach focuses on using frequency maps (hashmaps) to account for unmatched elements between the baskets. By using frequency counts and balancing the excesses in both baskets, we aim to minimize the swaps required.
This C implementation uses two arrays to keep track of frequencies of costs in each basket. Imbalances are corrected by finding differences and calculating costs using these differences.
Complexity
Time Complexity: O(n + m), where m is the maximum possible value in a basket.
Space Complexity: O(m), used for frequency arrays.
Approach 3: Greedy + Construction
First, we can remove the common elements from both arrays. For the remaining numbers, the occurrence of each number must be even, otherwise, it is impossible to construct identical arrays. Let's denote the arrays after removing common elements as a and b.
Next, we consider how to perform the swaps.
If we want to swap the smallest number in a, we need to find the largest number in b to swap with it; similarly, if we want to swap the smallest number in b, we need to find the largest number in a to swap with it. This can be achieved by sorting.
However, there is another swapping scheme. We can use a smallest number mi as a transition element, first swap the number in a with mi, and then swap mi with the number in b. In this way, the cost of swapping is 2 times mi.
In the code implementation, we can directly merge arrays a and b into an array nums, and then sort the array nums. Next, we enumerate the first half of the numbers, calculate the minimum cost each time, and add it to the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Compare | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Frequency Map Balancing | Time Complexity: O(n + m), where m is the maximum possible value in a basket. |
| Greedy + Construction | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare | O(n log n) | O(n) | When you explicitly track surplus fruits from both baskets and pair them after sorting. |
| Frequency Map Balancing | O(n log n) | O(n) | General case; easiest way to detect imbalance using hash maps and build swap candidates. |
Video Solution
Rearranging Fruits | Detailed Explanation | Minute Details | Leetcode 2561 | codestorywithMIK • codestorywithMIK • 12,164 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Rearranging Fruits easy or hard?
Rearranging Fruits Python/Java solution
How to solve Rearranging Fruits in O(n)?
What is the best approach for Rearranging Fruits?
Is Rearranging Fruits asked at Google/Amazon/Meta?
What data structure is used in Rearranging Fruits?
What is the time complexity of Rearranging Fruits?
Ready to solve this problem?
Practice Rearranging Fruits with our built-in code editor and test cases.
Practice on FleetCode