The Rearranging Fruits problem involves making two baskets of fruits identical by swapping fruits between the baskets. Each swap has a cost, and the goal is to minimize the total cost of swaps. If it is impossible to make the baskets identical, return -1
.
import java.util.*;
class Solution {
public long minCostToMakeIdentical(int[] basket1, int[] basket2) {
// Use a generic Map to avoid raw types
Map freq = new HashMap<>();
// Count the frequency of fruits in basket1
for (int fruit : basket1) {
freq.put(fruit, freq.getOrDefault(fruit, 0) + 1);
}
// Subtract the frequency of fruits in basket2
for (int fruit : basket2) {
freq.put(fruit, freq.getOrDefault(fruit, 0) - 1);
}
// Check if making baskets identical is possible
for (int count : freq.values()) {
if (count % 2 != 0) return -1; // Impossible if any fruit count is odd
}
// Collect excess fruits
List excess = new ArrayList<>();
for (Map.Entry entry : freq.entrySet()) {
int fruit = entry.getKey();
int count = Math.abs(entry.getValue()) / 2;
for (int i = 0; i < count; i++) {
excess.add(fruit);
}
}
// Sort excess fruits
Collections.sort(excess);
int minFruit = Math.min(Arrays.stream(basket1).min().getAsInt(), Arrays.stream(basket2).min().getAsInt());
long minCost = 0;
// Calculate the minimum cost
for (int i = 0; i < excess.size() / 2; i++) {
minCost += Math.min(excess.get(i), 2 * minFruit);
}
return minCost;
}
}
O(N)
, where N
is the total number of fruits.O(M log M)
, where M
is the number of unique fruit types.O(N + M log M)
.Input: basket1 = [1, 2, 3], basket2 = [2, 3, 1]
Output: 1
Explanation:
- Swap fruit 1 from basket1 with fruit 2 from basket2 at a cost of 1.