Rearranging Fruits

Hard

#2341Time: O(k^3) using a standard implementation of the Hungarian algorithm, where k is the number of swaps. Since k can be up to N/2, the complexity is O(N^3) in the worst case.Space: O(k^2), where k is the number of items to swap. In the worst case, k can be O(N), leading to O(N^2) space for the cost matrix.

Patterns

Greedy

Data structures

Array Hash Table

Prompt

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 i and j, and swap the ith fruit of basket1 with the jth fruit of basket2.
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.length
1 <= basket1.length <= 10⁵
1 <= basket1[i],basket2[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem as a classic assignment problem, which can be solved by finding a minimum weight perfect matching in a bipartite graph. First, we determine which fruits are 'misplaced'—that is, which fruits are in excess in one basket and deficient in the other. The set of excess fruits from basket1 forms one partition of our bipartite graph, and the set of excess fruits from basket2 forms the other. The weight of an edge between a fruit c1 from basket1 and a fruit c2 from basket2 is the cost of swapping them. This cost is the minimum of a direct swap, min(c1, c2), and an indirect swap using the cheapest fruit in the system as an intermediary, 2 * min_cost. The problem then reduces to finding a perfect matching between the two sets of fruits that minimizes the total cost (sum of edge weights).

Algorithm

Count the frequency of each fruit cost in basket1 and basket2.
Combine the frequencies to get the total count for each fruit cost across both baskets. If any fruit cost has an odd total count, it's impossible to make the baskets equal, so return -1.
Identify the fruits that need to be moved. Create a list to_swap_1 for fruits in excess in basket1 and to_swap_2 for fruits in excess in basket2. Let the number of fruits to be swapped be k.
Find the minimum fruit cost min_cost present in either basket.
Construct a k x k cost matrix C, where C[i][j] is the cost of swapping the i-th fruit from to_swap_1 with the j-th fruit from to_swap_2. The cost is min(min(to_swap_1[i], to_swap_2[j]), 2 * min_cost).
Use an algorithm for the assignment problem, like the Hungarian algorithm, to find the minimum weight perfect matching in the bipartite graph represented by the cost matrix.
The result of the assignment problem is the minimum total cost.

Walkthrough

The core idea is to formally define the swapping problem in terms of graph theory. We need to perform a series of swaps to balance the baskets. Each swap involves one fruit that basket1 needs to get rid of and one fruit that basket2 needs to get rid of. This is a one-to-one assignment.

We can represent the fruits to be moved from basket1 as one set of vertices, and those from basket2 as another. A complete bipartite graph is formed where edges represent potential swaps. The weight of each edge is the cost of that specific swap. The goal is to select a set of k edges (a perfect matching) such that every vertex is touched exactly once and the sum of the weights of these edges is minimized. This is a standard problem in computer science known as the assignment problem or min-weight bipartite matching, often solved with the Hungarian algorithm or min-cost max-flow algorithms. While correct, this method is not practical for the given constraints due to its high computational complexity.

1// This is a conceptual illustration. A full implementation of the Hungarian2// algorithm is complex and not provided here due to its inefficiency for this problem.3import java.util.*;4 5class Solution {6    public long minCost(int[] basket1, int[] basket2) {7        // Step 1 & 2: Count frequencies and check possibility8        Map<Integer, Integer> counts = new HashMap<>();9        for (int fruit : basket1) counts.put(fruit, counts.getOrDefault(fruit, 0) + 1);10        for (int fruit : basket2) counts.put(fruit, counts.getOrDefault(fruit, 0) + 1);11 12        for (int count : counts.values()) {13            if (count % 2 != 0) {14                return -1;15            }16        }17 18        // Step 3: Identify fruits to swap19        Map<Integer, Integer> counts1 = new HashMap<>();20        for (int fruit : basket1) counts1.put(fruit, counts1.getOrDefault(fruit, 0) + 1);21 22        List<Integer> to_swap_1 = new ArrayList<>();23        List<Integer> to_swap_2 = new ArrayList<>();24 25        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {26            int fruit = entry.getKey();27            int totalCount = entry.getValue();28            int count1 = counts1.getOrDefault(fruit, 0);29            int diff = count1 - totalCount / 2;30 31            if (diff > 0) {32                for (int i = 0; i < diff; i++) to_swap_1.add(fruit);33            } else if (diff < 0) {34                for (int i = 0; i < -diff; i++) to_swap_2.add(fruit);35            }36        }37 38        // If no swaps needed, cost is 039        if (to_swap_1.isEmpty()) {40            return 0;41        }42 43        // Step 4, 5, 6: This is where the heavyweight algorithm would be used.44        // The following is a placeholder for a call to a hypothetical Hungarian algorithm solver.45        // long totalCost = solveAssignmentProblem(to_swap_1, to_swap_2);46        // return totalCost;47 48        // Due to the high complexity, this approach is not feasible and a greedy approach is preferred.49        return -1; // Placeholder for non-implementation50    }51 52    // A hypothetical solver for the assignment problem.53    // private long solveAssignmentProblem(List<Integer> list1, List<Integer> list2) {54    //     // ... implementation of Hungarian Algorithm O(k^3) ...55    // }56}

Complexity

Time

O(k^3) using a standard implementation of the Hungarian algorithm, where k is the number of swaps. Since k can be up to N/2, the complexity is O(N^3) in the worst case.

Space

O(k^2), where k is the number of items to swap. In the worst case, k can be O(N), leading to O(N^2) space for the cost matrix.

Trade-offs

Pros

Provides a correct and general framework for solving assignment-type problems.
Guaranteed to find the optimal solution.

Cons

The time complexity of O(N^3) is too high for the given constraints (N up to 10^5), and will result in a 'Time Limit Exceeded' error.
The space complexity of O(N^2) can also be prohibitive for large N.
It's an overly complicated solution for a problem that has a much simpler and more efficient greedy solution.

A more efficient method is a greedy approach. The core insight is that to minimize the total swap cost, we should be strategic about which fruits we pair up for swapping. The problem of minimizing the sum of min(c1, c2) over all pairs is solved by pairing the smallest-cost fruits from one swap list with the largest-cost fruits from the other. This is a classic result related to the rearrangement inequality.

This approach first identifies the multisets of fruits that need to be moved from basket1 to basket2 and vice-versa. Then, it sorts one list of costs ascendingly and the other descendingly. By pairing the elements at the same index from these two sorted lists, we ensure an optimal pairing for direct swaps. For each such pair, we also consider a second option: instead of a direct swap, we can use the globally cheapest fruit as an intermediary, which costs 2 * min_cost. We take the cheaper of these two options for each pair of fruits that need to be swapped.

Algorithm

Use two HashMaps, counts1 and counts2, to store the frequency of each fruit cost in basket1 and basket2 respectively. Also, find the global minimum fruit cost, min_cost.
Create a combined frequency map for all fruits. Iterate through this map to check if all fruit types have an even total count. If any count is odd, return -1.
Create two lists, to_swap_1 and to_swap_2, to hold the costs of fruits that need to be moved out of basket1 and basket2 respectively.
Iterate through the combined frequency map. For each fruit c, calculate how many c's are in excess in one basket. Add c to the appropriate swap list that many times. For example, if basket1 has d excess fruits of cost c, add c to to_swap_1 d times.
Sort to_swap_1 in ascending order and to_swap_2 in descending order. This is the crucial greedy step.
Initialize total_cost = 0.
Iterate from i = 0 to k-1 (where k is the number of swaps). In each iteration, we pair the i-th element of to_swap_1 with the i-th element of to_swap_2.
The cost for swapping this pair (c1, c2) is min(min(c1, c2), 2 * min_cost). The 2 * min_cost term represents the alternative of using the cheapest fruit as an intermediary for two separate swaps.
Add this cost to total_cost.
Return total_cost.

Walkthrough

First, we must check if it's possible to make the baskets equal. This is done by counting the total frequency of each fruit cost. If any fruit cost appears an odd number of times in total, we can't distribute it evenly, so we return -1. Otherwise, a solution exists.

We then determine the 'swap lists': to_swap_1 contains costs of fruits that basket1 has in excess, and to_swap_2 for basket2. To minimize the sum of swap costs, we apply a greedy strategy. Let's say we need to swap k fruits. We sort to_swap_1 ascendingly and to_swap_2 descendingly. Then we iterate through them, pairing to_swap_1[i] with to_swap_2[i]. The cost for this pair is min(to_swap_1[i], to_swap_2[i]). However, we can always use the globally cheapest fruit (min_cost) as an intermediary. Swapping a fruit c with min_cost costs min_cost. To exchange a fruit from basket1 and another from basket2, we can do two such swaps via min_cost, for a total cost of 2 * min_cost. So, for each pair, we take min(direct_swap_cost, 2 * min_cost). Summing these up gives the total minimum cost.

1import java.util.*;2 3class Solution {4    public long minCost(int[] basket1, int[] basket2) {5        Map<Integer, Integer> allCounts = new HashMap<>();6        int minCost = Integer.MAX_VALUE;7 8        for (int fruit : basket1) {9            allCounts.put(fruit, allCounts.getOrDefault(fruit, 0) + 1);10            minCost = Math.min(minCost, fruit);11        }12        for (int fruit : basket2) {13            allCounts.put(fruit, allCounts.getOrDefault(fruit, 0) + 1);14            minCost = Math.min(minCost, fruit);15        }16 17        for (int count : allCounts.values()) {18            if (count % 2 != 0) {19                return -1;20            }21        }22 23        Map<Integer, Integer> counts1 = new HashMap<>();24        for (int fruit : basket1) {25            counts1.put(fruit, counts1.getOrDefault(fruit, 0) + 1);26        }27 28        List<Integer> toSwap1 = new ArrayList<>();29        List<Integer> toSwap2 = new ArrayList<>();30 31        for (Map.Entry<Integer, Integer> entry : allCounts.entrySet()) {32            int fruit = entry.getKey();33            int totalCount = entry.getValue();34            int count1 = counts1.getOrDefault(fruit, 0);35            int diff = count1 - totalCount / 2;36 37            if (diff > 0) {38                for (int i = 0; i < diff; i++) {39                    toSwap1.add(fruit);40                }41            } else if (diff < 0) {42                for (int i = 0; i < -diff; i++) {43                    toSwap2.add(fruit);44                }45            }46        }47 48        Collections.sort(toSwap1);49        Collections.sort(toSwap2, Collections.reverseOrder());50 51        long cost = 0;52        for (int i = 0; i < toSwap1.size(); i++) {53            int c1 = toSwap1.get(i);54            int c2 = toSwap2.get(i);55            cost += Math.min(Math.min(c1, c2), 2 * minCost);56        }57 58        return cost;59    }60}

Complexity

Time

O(N log N), dominated by the sorting of the swap lists. Populating frequency maps and iterating through them takes O(N) time. The size of the swap lists can be at most N, so sorting takes O(N log N).

Space

O(N) in the worst case. The frequency maps can store up to O(N) unique elements, and the swap lists can contain up to O(N) elements in total.

Trade-offs

Pros

Highly efficient with O(N log N) time complexity, which passes the given constraints.
The greedy strategy is proven to be optimal for this problem structure.
Implementation is relatively straightforward using standard library data structures and sorting.

Cons

The logic involving the 2 * min_cost can be subtle to reason about.
Requires sorting, which adds an O(N log N) factor to the time complexity.

Solutions

Solution

1class Solution {2public3  long minCost(int[] basket1, int[] basket2) {4    int n = basket1.length;5    Map<Integer, Integer> cnt = new HashMap<>();6    for (int i = 0; i < n; ++i) {7      cnt.merge(basket1[i], 1, Integer : : sum);8      cnt.merge(basket2[i], -1, Integer : : sum);9    }10    int mi = 1 << 30;11    List<Integer> nums = new ArrayList<>();12    for (var e : cnt.entrySet()) {13      int x = e.getKey(), v = e.getValue();14      if (v % 2 != 0) {15        return -1;16      }17      for (int i = Math.abs(v) / 2; i > 0; --i) {18        nums.add(x);19      }20      mi = Math.min(mi, x);21    }22    Collections.sort(nums);23    int m = nums.size();24    long ans = 0;25    for (int i = 0; i < m / 2; ++i) {26      ans += Math.min(nums.get(i), mi * 2);27    }28    return ans;29  }30}

1class Solution {2public:3  long long minCost(vector<int> &basket1, vector<int> &basket2) {4    int n = basket1.size();5    unordered_map<int, int> cnt;6    for (int i = 0; i < n; ++i) {7      cnt[basket1[i]]++;8      cnt[basket2[i]]--;9    }10    int mi = 1 << 30;11    vector<int> nums;12    for (auto &[x, v] : cnt) {13      if (v % 2) {14        return -1;15      }16      for (int i = abs(v) / 2; i; --i) {17        nums.push_back(x);18      }19      mi = min(mi, x);20    }21    sort(nums.begin(), nums.end());22    int m = nums.size();23    long long ans = 0;24    for (int i = 0; i < m / 2; ++i) {25      ans += min(nums[i], mi * 2);26    }27    return ans;28  }29};

1class Solution:2    def minCost(self, basket1: List[int], basket2: List[int]) -> int: cnt = Counter() for a, b in zip(basket1, basket2): cnt[a] += 1 cnt[b] -= 1 mi = min(cnt) nums = [] for x, v in cnt . items(): if v % 2: return - 1 nums . extend([x] * (abs(v) // 2)) nums . sort() m = len(nums) // 2 return sum(min(x, mi * 2) for x in nums[: m])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem