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] <= 109Problem 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.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we sort in-place.
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.
Time Complexity: O(n + m), where m is the maximum possible value in a basket.
Space Complexity: O(m), used for frequency arrays.
| 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. |
| 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. |
Rearranging Fruits | Detailed Explanation | Minute Details | Leetcode 2561 | codestorywithMIK • codestorywithMIK • 11,816 views views
Watch 9 more video solutions →Practice Rearranging Fruits with our built-in code editor and test cases.
Practice on FleetCode