# Rearranging Fruits
**Difficulty:** HARD
[External](https://leetcode.com/problems/rearranging-fruits)
Canonical: https://scaleengineer.com/dsa/problems/rearranging-fruits
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
---
## Problem
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 <= 105`
* `1 <= basket1[i],basket2[i] <= 109`

# Approaches
## Bipartite Matching (Assignment Problem)
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).
**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.
**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.
### Explanation
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.

```java
// This is a conceptual illustration. A full implementation of the Hungarian
// algorithm is complex and not provided here due to its inefficiency for this problem.
import java.util.*;

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        // Step 1 & 2: Count frequencies and check possibility
        Map<Integer, Integer> counts = new HashMap<>();
        for (int fruit : basket1) counts.put(fruit, counts.getOrDefault(fruit, 0) + 1);
        for (int fruit : basket2) counts.put(fruit, counts.getOrDefault(fruit, 0) + 1);

        for (int count : counts.values()) {
            if (count % 2 != 0) {
                return -1;
            }
        }

        // Step 3: Identify fruits to swap
        Map<Integer, Integer> counts1 = new HashMap<>();
        for (int fruit : basket1) counts1.put(fruit, counts1.getOrDefault(fruit, 0) + 1);

        List<Integer> to_swap_1 = new ArrayList<>();
        List<Integer> to_swap_2 = new ArrayList<>();

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int fruit = entry.getKey();
            int totalCount = entry.getValue();
            int count1 = counts1.getOrDefault(fruit, 0);
            int diff = count1 - totalCount / 2;

            if (diff > 0) {
                for (int i = 0; i < diff; i++) to_swap_1.add(fruit);
            } else if (diff < 0) {
                for (int i = 0; i < -diff; i++) to_swap_2.add(fruit);
            }
        }

        // If no swaps needed, cost is 0
        if (to_swap_1.isEmpty()) {
            return 0;
        }

        // Step 4, 5, 6: This is where the heavyweight algorithm would be used.
        // The following is a placeholder for a call to a hypothetical Hungarian algorithm solver.
        // long totalCost = solveAssignmentProblem(to_swap_1, to_swap_2);
        // return totalCost;

        // Due to the high complexity, this approach is not feasible and a greedy approach is preferred.
        return -1; // Placeholder for non-implementation
    }

    // A hypothetical solver for the assignment problem.
    // private long solveAssignmentProblem(List<Integer> list1, List<Integer> list2) {
    //     // ... implementation of Hungarian Algorithm O(k^3) ...
    // }
}
```
### Algorithm
1.  Count the frequency of each fruit cost in `basket1` and `basket2`.
2.  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.
3.  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`.
4.  Find the minimum fruit cost `min_cost` present in either basket.
5.  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)`.
6.  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.
7.  The result of the assignment problem is the minimum total cost.

## Greedy Approach with Sorting
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.
**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.
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        Map<Integer, Integer> allCounts = new HashMap<>();
        int minCost = Integer.MAX_VALUE;

        for (int fruit : basket1) {
            allCounts.put(fruit, allCounts.getOrDefault(fruit, 0) + 1);
            minCost = Math.min(minCost, fruit);
        }
        for (int fruit : basket2) {
            allCounts.put(fruit, allCounts.getOrDefault(fruit, 0) + 1);
            minCost = Math.min(minCost, fruit);
        }

        for (int count : allCounts.values()) {
            if (count % 2 != 0) {
                return -1;
            }
        }

        Map<Integer, Integer> counts1 = new HashMap<>();
        for (int fruit : basket1) {
            counts1.put(fruit, counts1.getOrDefault(fruit, 0) + 1);
        }

        List<Integer> toSwap1 = new ArrayList<>();
        List<Integer> toSwap2 = new ArrayList<>();

        for (Map.Entry<Integer, Integer> entry : allCounts.entrySet()) {
            int fruit = entry.getKey();
            int totalCount = entry.getValue();
            int count1 = counts1.getOrDefault(fruit, 0);
            int diff = count1 - totalCount / 2;

            if (diff > 0) {
                for (int i = 0; i < diff; i++) {
                    toSwap1.add(fruit);
                }
            } else if (diff < 0) {
                for (int i = 0; i < -diff; i++) {
                    toSwap2.add(fruit);
                }
            }
        }

        Collections.sort(toSwap1);
        Collections.sort(toSwap2, Collections.reverseOrder());

        long cost = 0;
        for (int i = 0; i < toSwap1.size(); i++) {
            int c1 = toSwap1.get(i);
            int c2 = toSwap2.get(i);
            cost += Math.min(Math.min(c1, c2), 2 * minCost);
        }

        return cost;
    }
}
```
### Algorithm
1.  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`.
2.  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.
3.  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.
4.  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.
5.  Sort `to_swap_1` in ascending order and `to_swap_2` in descending order. This is the crucial greedy step.
6.  Initialize `total_cost = 0`.
7.  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`.
8.  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.
9.  Add this cost to `total_cost`.
10. Return `total_cost`.

# Solutions
### Java

```java
class Solution {
public
  long minCost(int[] basket1, int[] basket2) {
    int n = basket1.length;
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      cnt.merge(basket1[i], 1, Integer : : sum);
      cnt.merge(basket2[i], -1, Integer : : sum);
    }
    int mi = 1 << 30;
    List<Integer> nums = new ArrayList<>();
    for (var e : cnt.entrySet()) {
      int x = e.getKey(), v = e.getValue();
      if (v % 2 != 0) {
        return -1;
      }
      for (int i = Math.abs(v) / 2; i > 0; --i) {
        nums.add(x);
      }
      mi = Math.min(mi, x);
    }
    Collections.sort(nums);
    int m = nums.size();
    long ans = 0;
    for (int i = 0; i < m / 2; ++i) {
      ans += Math.min(nums.get(i), mi * 2);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minCost(vector<int> &basket1, vector<int> &basket2) {
    int n = basket1.size();
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
      cnt[basket1[i]]++;
      cnt[basket2[i]]--;
    }
    int mi = 1 << 30;
    vector<int> nums;
    for (auto &[x, v] : cnt) {
      if (v % 2) {
        return -1;
      }
      for (int i = abs(v) / 2; i; --i) {
        nums.push_back(x);
      }
      mi = min(mi, x);
    }
    sort(nums.begin(), nums.end());
    int m = nums.size();
    long long ans = 0;
    for (int i = 0; i < m / 2; ++i) {
      ans += min(nums[i], mi * 2);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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])

```