LeetCode 2561 - Rearranging Fruits

LeetCode Problem 2561

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Greedy, Sort

Solution

Problem Understanding

This problem gives us two arrays, basket1 and basket2, where each element represents the cost of a fruit in a basket. Both baskets contain exactly n fruits. Our goal is to make the two baskets equal, where equality means that after sorting both arrays, they contain exactly the same multiset of values.

We are allowed to repeatedly swap one fruit from basket1 with one fruit from basket2. The cost of a swap is the minimum of the two swapped fruit values.

The important detail is that basket order does not matter. Only the final frequency of each fruit value matters. This means we are effectively transforming the frequency distribution of the two baskets until they match.

The task is to compute the minimum total swap cost needed to make the baskets equal. If it is impossible, we return -1.

The constraints are large:

• Up to 10^5 elements
• Fruit values up to 10^9

These constraints immediately rule out any exponential or quadratic brute-force simulation. We need an algorithm close to O(n log n).

A key observation is that every fruit value must appear an even number of times across both baskets combined. If some value appears an odd number of times overall, there is no way to distribute it equally between the two baskets, so the answer is -1.

Some important edge cases include:

• The baskets are already equal, so the answer is 0
• A fruit value appears an odd number of times globally
• Swapping directly is more expensive than using an intermediate smallest fruit
• Large duplicate groups
• Extremely large fruit values that require careful cost minimization

Approaches

Brute Force Approach

A brute-force strategy would attempt to simulate swaps between baskets until the frequency distributions match. One possible implementation would repeatedly locate mismatched values and try all possible swaps to determine the minimum cost arrangement.

This works conceptually because eventually every imbalance can be corrected through swaps. However, the number of possible swap sequences grows extremely quickly. Even greedy local choices are difficult to evaluate without considering future consequences.

If we attempted all pairings of mismatched fruits, the complexity could easily become quadratic or worse. With n = 10^5, this is far too slow.

Key Insight for the Optimal Solution

The important insight is that we do not need to simulate the actual basket states. Instead, we only care about which extra values must move from one basket to the other.

Suppose a value appears more times in basket1 than in basket2. Then some copies of that value must be swapped out. Similarly, if a value appears more times in basket2, some copies must be swapped in.

We can collect:

• Extra values from basket1
• Extra values from basket2

These lists must be paired and swapped.

Another crucial optimization comes from observing that direct swaps are not always optimal.

Suppose we want to swap a large value x with another large value y. Instead of swapping directly with cost min(x, y), we may achieve a cheaper result by using the globally smallest fruit value m as an intermediate:

1. Swap x with m
2. Swap m with y

This costs 2 * m.

Therefore, for every required swap, the minimum achievable cost is:

$$\min(\text{direct swap cost}, 2 \times \text{global minimum})$$

This transforms the problem into a sorting and pairing problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential or O(n²)	O(n)	Tries explicit swap simulation
Optimal	O(n log n)	O(n)	Uses frequency balancing and greedy pairing

Algorithm Walkthrough

1. Count the frequency of every fruit value across both baskets.

We use hash maps because fruit values can be as large as 10^9, making array indexing impractical. 2. Check feasibility.

For every fruit value, compute:

$$\text{count in basket1} + \text{count in basket2}$$

If this total is odd, return -1.

This is necessary because both baskets must eventually contain exactly half of the total occurrences. 3. Find the global minimum fruit value.

This value is important because it may be used as an intermediate swap to reduce cost. 4. Build mismatch lists.

For each fruit value:

• If basket1 has extra copies, add them to extra1
• If basket2 has extra copies, add them to extra2

The number of copies added is:

$$\frac{|\text{freq1} - \text{freq2}|}{2}$$

because each swap fixes two misplaced copies. 5. Sort the mismatch lists.

We sort:

• extra1 in ascending order
• extra2 in descending order

This pairing minimizes direct swap costs. 6. Compute the minimum cost.

For every pair (a, b):

• Direct swap cost is min(a, b)
• Indirect swap cost is 2 * globalMin

Add:

$$\min(\min(a, b), 2 \times globalMin)$$

to the answer. 7. Return the total cost.

Why it works

Every imbalance must eventually be corrected through swaps. The mismatch lists precisely capture which values must move between baskets.

Sorting and pairing smallest with largest minimizes direct swap costs greedily. Additionally, any expensive direct swap can always be replaced by two swaps involving the globally smallest fruit. Since every swap is independent after balancing frequencies, summing the locally minimal costs produces the globally minimal answer.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        freq1 = Counter(basket1)
        freq2 = Counter(basket2)

        all_values = set(freq1.keys()) | set(freq2.keys())

        global_min = min(min(basket1), min(basket2))

        extra1 = []
        extra2 = []

        for value in all_values:
            total = freq1[value] + freq2[value]

            if total % 2 != 0:
                return -1

            diff = freq1[value] - freq2[value]

            if diff > 0:
                extra1.extend([value] * (diff // 2))
            elif diff < 0:
                extra2.extend([value] * ((-diff) // 2))

        extra1.sort()
        extra2.sort(reverse=True)

        total_cost = 0

        for a, b in zip(extra1, extra2):
            direct_cost = min(a, b)
            indirect_cost = 2 * global_min

            total_cost += min(direct_cost, indirect_cost)

        return total_cost

The implementation begins by counting frequencies in both baskets using Counter. This allows constant-time lookup of how many times each fruit value appears.

We then iterate over all distinct fruit values and verify that the total occurrence count is even. If not, we immediately return -1.

Next, we compute which values are extra in each basket. If a value appears too many times in basket1, half of the difference must move to basket2. The same logic applies in reverse.

After collecting all excess values, we sort the lists strategically. Pairing the smallest surplus values from one side with the largest from the other minimizes swap cost.

Finally, for each required swap, we compare:

• Direct swap cost
• Indirect cost using the global minimum twice

The sum of these minimal costs is the final answer.

Go Solution

package main

import (
	"sort"
)

func minCost(basket1 []int, basket2 []int) int64 {
	freq1 := make(map[int]int)
	freq2 := make(map[int]int)

	globalMin := basket1[0]

	for _, v := range basket1 {
		freq1[v]++
		if v < globalMin {
			globalMin = v
		}
	}

	for _, v := range basket2 {
		freq2[v]++
		if v < globalMin {
			globalMin = v
		}
	}

	allValues := make(map[int]bool)

	for k := range freq1 {
		allValues[k] = true
	}

	for k := range freq2 {
		allValues[k] = true
	}

	extra1 := []int{}
	extra2 := []int{}

	for value := range allValues {
		total := freq1[value] + freq2[value]

		if total%2 != 0 {
			return -1
		}

		diff := freq1[value] - freq2[value]

		if diff > 0 {
			for i := 0; i < diff/2; i++ {
				extra1 = append(extra1, value)
			}
		} else if diff < 0 {
			for i := 0; i < (-diff)/2; i++ {
				extra2 = append(extra2, value)
			}
		}
	}

	sort.Ints(extra1)

	sort.Slice(extra2, func(i, j int) bool {
		return extra2[i] > extra2[j]
	})

	var totalCost int64 = 0

	for i := 0; i < len(extra1); i++ {
		a := extra1[i]
		b := extra2[i]

		directCost := min(a, b)
		indirectCost := 2 * globalMin

		totalCost += int64(min(directCost, indirectCost))
	}

	return totalCost
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version but uses native maps instead of Counter.

One important difference is that Go requires explicit integer type handling. Since the answer may become large, the function returns int64.

Slices are used to store the extra elements, and custom sorting is required for descending order on extra2.

Worked Examples

Example 1

basket1 = [4,2,2,2]
basket2 = [1,4,1,2]

Step 1: Frequency counts

Value	basket1	basket2
1	0	2
2	3	1
4	1	1

Step 2: Check parity

Value	Total Count	Even?
1	2	Yes
2	4	Yes
4	2	Yes

Possible.

Step 3: Build mismatch lists

For value 1:

• basket2 has 2 extra
• Need 1 copy moved

extra2 = [1]

For value 2:

• basket1 has 2 extra
• Need 1 copy moved

extra1 = [2]

Step 4: Sort

extra1 = [2]
extra2 = [1]

Global minimum:

1

Step 5: Compute cost

Pair (2,1):

Direct cost:

min(2,1) = 1

Indirect cost:

2 * 1 = 2

Choose minimum:

1

Final answer:

1

Example 2

basket1 = [2,3,4,1]
basket2 = [3,2,5,1]

Step 1: Frequency counts

Value	basket1	basket2
1	1	1
2	1	1
3	1	1
4	1	0
5	0	1

Step 2: Check parity

Value	Total Count	Even?
4	1	No
5	1	No

Since odd totals exist, equalization is impossible.

Return:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting mismatch lists dominates
Space	O(n)	Frequency maps and mismatch arrays

The frequency counting phase is linear. Constructing mismatch lists is also linear. The dominant cost comes from sorting the excess elements, which requires O(n log n) time in the worst case.

The auxiliary space usage comes from hash maps and the mismatch arrays.

Test Cases

from typing import List

s = Solution()

assert s.minCost([4,2,2,2], [1,4,1,2]) == 1  # Provided example
assert s.minCost([2,3,4,1], [3,2,5,1]) == -1  # Impossible case

assert s.minCost([1,1], [1,1]) == 0  # Already equal

assert s.minCost([1,2], [2,1]) == 0  # Equal after sorting

assert s.minCost([1,1,2,2], [1,1,2,2]) == 0  # Identical baskets

assert s.minCost([1,1,1,2], [2,2,2,1]) == 1  # Single cheap swap

assert s.minCost([10,10,10,1], [20,20,20,1]) == -1  # Odd total frequencies

assert s.minCost([1,1000], [500,500]) == -1  # Impossible balancing

assert s.minCost([1,1,100,100], [1,1,200,200]) == 2  # Indirect swap cheaper

assert s.minCost([1,2,2,2], [1,1,1,2]) == 1  # Minimal swap

assert s.minCost([5,5,5,5], [5,5,5,5]) == 0  # All same values

assert s.minCost([1,1,2,2,3,3], [1,1,2,2,3,3]) == 0  # Multiple duplicates

assert s.minCost([1,1,1,1,100,100], [1,1,50,50,50,50]) == 2  # Use global minimum

Test	Why
[4,2,2,2] vs [1,4,1,2]	Validates basic swap logic
[2,3,4,1] vs [3,2,5,1]	Validates impossible detection
Already equal baskets	Ensures zero-cost handling
Equal after sorting	Confirms order independence
Large duplicate groups	Tests frequency balancing
Single cheap swap	Validates direct swap cost
Odd total frequencies	Ensures impossibility logic
Large values	Tests high-value handling
Indirect swap cheaper	Validates global minimum optimization
Mixed duplicates	Tests balancing correctness
Uniform baskets	Ensures stable behavior
Multiple repeated values	Stress-tests counting logic
Intermediate swap optimization	Confirms greedy cost minimization

Edge Cases

One important edge case occurs when a fruit value appears an odd number of times across both baskets. Since both baskets must end with identical frequency distributions, every value must be divisible evenly between the two baskets. A naive implementation might attempt swaps anyway, but the correct behavior is to immediately return -1. The implementation explicitly checks parity before doing any swap calculations.

Another subtle edge case occurs when direct swaps are more expensive than routing through the globally smallest fruit. For example, swapping 100 and 200 directly costs 100, but using a global minimum fruit 1 costs only 2. Implementations that only consider direct swaps will produce incorrect answers. The algorithm handles this by always taking the minimum of direct cost and 2 * globalMin.

A third important edge case involves baskets that are already equal after sorting. Since order does not matter, arrays like [1,2] and [2,1] require zero operations. A naive position-based algorithm might incorrectly attempt swaps. This implementation works entirely with frequencies, so it naturally handles such cases correctly.

A final edge case involves large duplicate groups. If one basket contains many extra copies of the same value, it is easy to accidentally overcount required swaps. The algorithm correctly adds only half the frequency difference because each swap fixes one misplaced element in each basket simultaneously.