โ† Back to Index

๐Ÿ“š Rearranging Fruits โ€“ Java Cheat Sheet

๐Ÿ“Œ What Is It?

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.

๐Ÿงฑ Pattern Template

Greedy Algorithm with Frequency Count

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;
    }
}

๐Ÿ“Š Time Complexity

โœ… Use Cases

๐Ÿ“˜ Common LeetCode Problems

๐Ÿงช Example

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.

๐Ÿ’ก Pro Tips