Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each fruit value must be split equally between the baskets, so an odd frequency imbalance makes the task impossible. A needed swap can be done directly at the smaller fruit's cost, or through the globally cheapest fruit in two swaps at twice that minimum cost.

Approach

Compute the frequency difference between baskets and the global minimum fruit value. Reject any odd difference. Collect abs(difference)/2 copies of each imbalanced value and sort this combined list. If its length is 2q, each basket contributes q surplus fruits. When the smaller half contains a from basket one, the larger half contains exactly a from basket two; the other counts also match. Thus every smaller-half value can be paired with an opposite-basket value from the larger half. Sum min(value, 2*globalMinimum) over the smaller half, achieving the cheapest possible exchange minima. Already-balanced baskets contribute zero.

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        n = len(basket1)
        freq = defaultdict(int)
        mn = float('inf')

        for i in range(n):
            freq[basket1[i]] += 1
            freq[basket2[i]] -= 1
            mn = min(mn, basket1[i], basket2[i])

        to_swap = []
        for k, v in freq.items():
            if v % 2 != 0:
                return -1
            to_swap += [k] * (abs(v) // 2)

        to_swap.sort()
        res = 0

        for i in range(len(to_swap) // 2):
            res += min(to_swap[i], 2 * mn)

        return res

Complexity analysis

Let n = basket1.length, u be the number of distinct fruit values, and s the length of the swap-candidate list (s <= n). Time: O(n + u + s log s). Auxiliary space: O(u + s).