In this problem, we're given two baskets of fruits, each represented by a list of integers where each integer denotes the cost of a fruit. Our goal is to make the two baskets identical (after sorting) by swapping elements between them. Each swap costs the minimum of the two values being swapped. The objective is to perform the swaps at the minimum total cost, or return -1 if it's impossible.
Problem Statement
Given two arrays basket1 and basket2 of equal length, each containing the cost of fruits, return the minimum total cost to make the baskets identical through any number of swaps. If it's not possible, return -1.
Approach
To solve the problem:
- Sort both arrays. This helps in aligning and comparing values easily.
- Use two pointers to walk through both sorted arrays.
- If a mismatch is found, collect the extra fruits that need to be swapped.
- Validate that the frequency of mismatched values is even (because we need to swap in pairs).
- Find the minimal cost by either directly swapping mismatches or using a double-swap via the globally smallest fruit cost (a helpful trick to reduce cost).
This approach ensures correctness while optimizing cost using the minimum swap rule.
C++ Implementation
class Solution {
public:
long long minCost(vector<int>& basket1, vector<int>& basket2) {
int n = basket1.size();
auto & u = basket1;
auto & w = basket2;
sort(u.begin(), u.end());
sort(w.begin(), w.end());
int a = min(u[0], w[0]);
a <<= 1;
int i = 0, j = 0, k = 0, l = 0;
while(i<n && j<n) {
if (u[i] == w[j]) { i++; j++; }
else if (u[i] < w[j]) {
if (i == n-1 || u[i] != u[i+1]) return -1;
u[k++] = u[i];
i += 2;
} else {
if (j == n-1 || w[j] != w[j+1]) return -1;
w[l++] = w[j];
j += 2;
}
}
while (i<n) {
if (u[i] != u[i+1]) return -1;
u[k++] = u[i];
i += 2;
}
while (j<n) {
if (w[j] != w[j+1]) return -1;
w[l++] = w[j];
j += 2;
}
long long rt = 0;
for (i=0; i<k; i++) {
rt += min(min(u[i], w[k-1-i]), (long long)a);
}
return rt;
}
};
JavaScript Implementation
var minCost = function(basket1, basket2) {
basket1.sort((a, b) => a - b);
basket2.sort((a, b) => a - b);
let n = basket1.length, a = Math.min(basket1[0], basket2[0]) * 2;
let i = 0, j = 0, u = [], w = [];
while (i < n && j < n) {
if (basket1[i] === basket2[j]) { i++; j++; }
else if (basket1[i] < basket2[j]) {
if (i + 1 >= n || basket1[i] !== basket1[i + 1]) return -1;
u.push(basket1[i]); i += 2;
} else {
if (j + 1 >= n || basket2[j] !== basket2[j + 1]) return -1;
w.push(basket2[j]); j += 2;
}
}
while (i < n) {
if (i + 1 >= n || basket1[i] !== basket1[i + 1]) return -1;
u.push(basket1[i]); i += 2;
}
while (j < n) {
if (j + 1 >= n || basket2[j] !== basket2[j + 1]) return -1;
w.push(basket2[j]); j += 2;
}
let res = 0;
for (let k = 0; k < u.length; k++) {
res += Math.min(u[k], w[u.length - 1 - k], a);
}
return res;
};
Python Implementation
def minCost(basket1, basket2):
basket1.sort()
basket2.sort()
n = len(basket1)
a = min(basket1[0], basket2[0]) * 2
u, w = [], []
i = j = 0
while i < n and j < n:
if basket1[i] == basket2[j]:
i += 1
j += 1
elif basket1[i] < basket2[j]:
if i+1 >= n or basket1[i] != basket1[i+1]: return -1
u.append(basket1[i])
i += 2
else:
if j+1 >= n or basket2[j] != basket2[j+1]: return -1
w.append(basket2[j])
j += 2
while i < n:
if i+1 >= n or basket1[i] != basket1[i+1]: return -1
u.append(basket1[i])
i += 2
while j < n:
if j+1 >= n or basket2[j] != basket2[j+1]: return -1
w.append(basket2[j])
j += 2
res = 0
for k in range(len(u)):
res += min(u[k], w[-1-k], a)
return res
Time and Space Complexity
-
Time Complexity:
O(n log n)due to sorting both arrays. -
Space Complexity:
O(n)for storing unmatched items that need to be swapped.
My Thoughts
The key to solving this problem lies in realizing that mismatched values must occur in pairs to be swapped. Using the smallest global element cost to reduce the swap cost cleverly avoids higher swap penalties. This approach avoids brute force pairing and ensures that cost is minimized in a structured way. One tricky part is validating swap feasibility based on frequency—this check is crucial before even thinking about costs.
Overall, a well-structured greedy approach with sorting and two-pointer traversal leads to an efficient and correct solution.
Top comments (3)
Missed your leetcode Series ❤️
Thanks Anna!
Yeah it is very intresting, nowadays most of the India based game development companies were also sharing such type of guides to keep gaming audience engaging.