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.

Examples

Example 1

1
2
3

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

1
2
3

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^5
  • 1 <= basket1[i],basket2[i] <= 10^9

Solution

Method 1 – Greedy with Counting and Swapping

Intuition

If the total count of each fruit is not even, it’s impossible. Otherwise, we can pair up the excess fruits in each basket and swap them, always using the cheapest possible swap (either direct or via the global minimum fruit).

Approach

  1. Count the frequency of each fruit in both baskets.
  2. For each fruit, if the total count is odd, return -1.
  3. For each fruit, compute the excess in basket1 and basket2 (half the difference for each direction).
  4. Collect all excess fruits to be swapped from both baskets.
  5. Sort the lists and pair the smallest with the largest, but always consider swapping via the global minimum fruit if it’s cheaper.
  6. Sum the minimum cost for each swap.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <unordered_map>
class Solution {
public:
    long long minCost(vector<int>& b1, vector<int>& b2) {
        unordered_map<int, int> cnt;
        for (int x : b1) cnt[x]++;
        for (int x : b2) cnt[x]--;
        vector<int> pos, neg;
        int mn = INT_MAX;
        for (auto& [k, v] : cnt) {
            mn = min(mn, k);
            if (v % 2 != 0) return -1;
            if (v > 0) for (int i = 0; i < v/2; ++i) pos.push_back(k);
            if (v < 0) for (int i = 0; i < -v/2; ++i) neg.push_back(k);
        }
        sort(pos.begin(), pos.end());
        sort(neg.rbegin(), neg.rend());
        long long ans = 0;
        for (int i = 0; i < pos.size(); ++i) {
            ans += min({pos[i], neg[i], 2*mn});
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import "sort"
func minCost(b1, b2 []int) int64 {
    cnt := map[int]int{}
    mn := int(1e9+1)
    for _, x := range b1 { cnt[x]++; if x < mn { mn = x } }
    for _, x := range b2 { cnt[x]--; if x < mn { mn = x } }
    pos, neg := []int{}, []int{}
    for k, v := range cnt {
        if v%2 != 0 { return -1 }
        for i := 0; i < abs(v)/2; i++ {
            if v > 0 { pos = append(pos, k) }
            if v < 0 { neg = append(neg, k) }
        }
    }
    sort.Ints(pos)
    sort.Sort(sort.Reverse(sort.IntSlice(neg)))
    var ans int64
    for i := range pos {
        x, y := pos[i], neg[i]
        if x < y {
            if x < 2*mn { ans += int64(x) } else { ans += int64(2*mn) }
        } else {
            if y < 2*mn { ans += int64(y) } else { ans += int64(2*mn) }
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.util.*;
class Solution {
    public long minCost(int[] b1, int[] b2) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int mn = Integer.MAX_VALUE;
        for (int x : b1) { cnt.put(x, cnt.getOrDefault(x, 0) + 1); mn = Math.min(mn, x); }
        for (int x : b2) { cnt.put(x, cnt.getOrDefault(x, 0) - 1); mn = Math.min(mn, x); }
        List<Integer> pos = new ArrayList<>(), neg = new ArrayList<>();
        for (var e : cnt.entrySet()) {
            int k = e.getKey(), v = e.getValue();
            if (v % 2 != 0) return -1;
            for (int i = 0; i < Math.abs(v)/2; ++i) {
                if (v > 0) pos.add(k);
                if (v < 0) neg.add(k);
            }
        }
        Collections.sort(pos);
        neg.sort(Collections.reverseOrder());
        long ans = 0;
        for (int i = 0; i < pos.size(); ++i) {
            ans += Math.min(Math.min(pos.get(i), neg.get(i)), 2*mn);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun minCost(b1: IntArray, b2: IntArray): Long {
        val cnt = mutableMapOf<Int, Int>()
        var mn = Int.MAX_VALUE
        for (x in b1) { cnt[x] = cnt.getOrDefault(x, 0) + 1; mn = minOf(mn, x) }
        for (x in b2) { cnt[x] = cnt.getOrDefault(x, 0) - 1; mn = minOf(mn, x) }
        val pos = mutableListOf<Int>()
        val neg = mutableListOf<Int>()
        for ((k, v) in cnt) {
            if (v % 2 != 0) return -1
            repeat(kotlin.math.abs(v)/2) {
                if (v > 0) pos.add(k)
                if (v < 0) neg.add(k)
            }
        }
        pos.sort()
        neg.sortDescending()
        var ans = 0L
        for (i in pos.indices) {
            ans += minOf(pos[i], neg[i], 2*mn)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minCost(self, basket1: list[int], basket2: list[int]) -> int:
        from collections import Counter
        cnt = Counter()
        mn = float('inf')
        for x in basket1:
            cnt[x] += 1
            mn = min(mn, x)
        for x in basket2:
            cnt[x] -= 1
            mn = min(mn, x)
        pos, neg = [], []
        for k, v in cnt.items():
            if v % 2 != 0:
                return -1
            if v > 0:
                pos += [k] * (v // 2)
            if v < 0:
                neg += [k] * (-v // 2)
        pos.sort()
        neg.sort(reverse=True)
        ans = 0
        for x, y in zip(pos, neg):
            ans += min(x, y, 2*mn)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::HashMap;
impl Solution {
    pub fn min_cost(basket1: Vec<i32>, basket2: Vec<i32>) -> i64 {
        let mut cnt = HashMap::new();
        let mut mn = i32::MAX;
        for &x in &basket1 { *cnt.entry(x).or_insert(0) += 1; mn = mn.min(x); }
        for &x in &basket2 { *cnt.entry(x).or_insert(0) -= 1; mn = mn.min(x); }
        let mut pos = vec![];
        let mut neg = vec![];
        for (&k, &v) in &cnt {
            if v % 2 != 0 { return -1; }
            for _ in 0..(v.abs()/2) {
                if v > 0 { pos.push(k); }
                if v < 0 { neg.push(k); }
            }
        }
        pos.sort();
        neg.sort_by(|a, b| b.cmp(a));
        let mut ans = 0i64;
        for i in 0..pos.len() {
            ans += pos[i].min(neg[i]).min(2*mn) as i64;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    minCost(basket1: number[], basket2: number[]): number {
        const cnt = new Map<number, number>();
        let mn = Infinity;
        for (const x of basket1) { cnt.set(x, (cnt.get(x)||0)+1); mn = Math.min(mn, x); }
        for (const x of basket2) { cnt.set(x, (cnt.get(x)||0)-1); mn = Math.min(mn, x); }
        const pos: number[] = [], neg: number[] = [];
        for (const [k, v] of cnt) {
            if (v % 2 !== 0) return -1;
            for (let i = 0; i < Math.abs(v)/2; ++i) {
                if (v > 0) pos.push(k);
                if (v < 0) neg.push(k);
            }
        }
        pos.sort((a, b) => a - b);
        neg.sort((a, b) => b - a);
        let ans = 0;
        for (let i = 0; i < pos.length; ++i) {
            ans += Math.min(pos[i], neg[i], 2*mn);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of the baskets, due to sorting the excess lists.
  • 🧺 Space complexity: O(n), for storing the excess fruits to be swapped.