2561. Rearranging Fruits


Problem Description

In this problem, we are given two fruit baskets with exactly n fruits each. These fruit baskets are represented by two integer arrays basket1 and basket2 where each element indicates the cost of the respective fruit. Our task is to make both baskets contain the exact same fruits in terms of their costs, which means that if we sort both baskets by their fruits' costs, they should look identical.

However, there are rules on how we can make the two baskets equal:

  1. We can choose to swap the i-th fruit from basket1 with the j-th fruit from basket2.
  2. The cost incurred for swapping these two fruits is min(basket1[i], basket2[j]).

The goal is to find the minimum total cost required to make both baskets equal through such swapping operations. If it's not possible to make both baskets equal, we should return -1.

Intuition

To solve this problem, we need to follow a series of logical steps:

  1. Frequency Counting: First, we use a frequency counter to understand the difference between the baskets in terms of fruit costs. For each matching pair of fruits (same cost in both baskets), there's no action required. If a fruit cost in basket1 is not counter-balanced by the same cost in basket2, then alternations are needed.

  2. Balancing Counts: We need to check if each fruit's imbalanced count is even. An odd imbalance means we cannot fully swap fruits to balance the baskets, so we return -1. For instance, an extra three fruits of cost 5 in basket1 cannot be balanced by swaps since we would always end up with an uncoupled fruit.

  3. Calculating Minimum Swap Cost: Since only pairs of unbalanced fruits need swapping, we sort the unbalanced fruits by their costs. We can then calculate the cost to swap half of these unbalanced fruits (each swap involves two fruits, hence 'half'). We choose either the cost of the current fruit or two times the minimum fruit cost for each swap, whichever is lesser, to ensure the lowest possible swap cost.

  4. Summation of Costs: Summing up the swap costs will result in the minimum cost required to balance the baskets.

By following the code provided according to the intuition above, we ensure that we're swapping fruits in the most cost-effective way possible, resulting in the minimum cost to make both baskets equal.

Learn more about Greedy patterns.

Solution Approach

Step-by-Step Implementation:

  1. Create a Counter Object: Using the Counter class from the collections module we create a cnt object to track the balance of fruits between basket1 and basket2. A positive value in cnt means there are more fruits of that cost in basket1 and vice versa.

  2. Zip and Update Counts: We iterate through basket1 and basket2 in tandem using zip:

    1for a, b in zip(basket1, basket2):
    2    cnt[a] += 1
    3    cnt[b] -= 1

    For each pair (a, b) of fruits, we increment the count of fruit a in cnt because it's from basket1, and decrement for fruit b because it's from basket2.

  3. Find the Minimum Cost Fruit: We find the minimum cost fruit that can be used for calculating the swap cost using min(cnt).

  4. Prepare List of Imbalanced Fruits: Iterate over the cnt to find the imbalances. If there's an odd imbalance, we cannot make a swap to balance the fruit, and therefore the task is impossible and we return -1:

    1nums = []
    2for x, v in cnt.items():
    3    if v % 2:
    4        return -1
    5    nums.extend([x] * (abs(v) // 2))

    We repeat the fruit cost value abs(v) // 2 times because we need pairs for swapping.

  5. Sort the List: Sorting the list of costs ensures that when we choose fruits to swap, we always consider the least costly.

    1nums.sort()
  6. Calculate the Cost for Half the Swaps: We only need to make swaps for half of the imbalanced fruits. For each imbalanced fruit cost, choose the lower of the fruit's cost itself or double the minimum cost fruit:

    1m = len(nums) // 2
    2total_cost = sum(min(x, mi * 2) for x in nums[:m])
  7. Return the Minimum Total Cost: Finally, we return the sum which represents the minimum cost to make both the baskets contain the same fruits.

By using a Counter to maintain the frequency of the fruits' costs, determining the least cost fruit for swap calculations, and leveraging sorting to guide our swapping strategy, we establish an efficient approach to determine the minimum swapping cost required—or recognize that balancing the baskets is infeasible.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's consider a small example to illustrate the solution approach with two fruit baskets basket1 and basket2, each with n=5 fruits:

1basket1 = [1, 3, 3, 2, 5]
2basket2 = [2, 1, 4, 3, 4]

We want to find the minimum total cost to make the fruits in both baskets have the same costs after swapping.

  1. Create a Counter Object: Create a counter to track the balance of fruits:

    1cnt = Counter()
  2. Zip and Update Counts: We compare basket1 and basket2 simultaneously and update our counter:

    1cnt[1] += 1   # From basket1
    2cnt[2] -= 1   # From basket2 (counterpart for basket1[1])
    3cnt[3] += 1   # From basket1
    4cnt[1] -= 1   # From basket2 (counterpart for basket1[3])
    5cnt[3] += 1   # From basket1
    6cnt[4] -= 1   # From basket2 (counterpart for basket1[3])
    7cnt[2] += 1   # From basket1
    8cnt[3] -= 1   # From basket2 (counterpart for basket1[2])
    9cnt[5] += 1   # From basket1
    10cnt[4] -= 1   # From basket2 (counterpart for basket1[5])
    11
    12After updating counts, `cnt` looks like this:
    13cnt = {1: 0, 3: 1, 2: 0, 4: -2, 5: 1}
  3. Find the Minimum Cost Fruit: The minimum fruit cost from the imbalanced fruits (cnt) is 3.

  4. Prepare List of Imbalanced Fruits: Check the imbalances and gather the fruits that need to be swapped:

    1nums = [3, 5]  # We need to swap one fruit with cost 3 and one with cost 5

    Since there are no odd values in cnt, we proceed.

  5. Sort the List: We sort the imbalances to ensure we consider the least costly fruits first:

    1nums.sort()
    2nums = [3, 5]
  6. Calculate the Cost for Half the Swaps: There are two imbalanced fruits, so we need one swap:

    1mi = 3  # minimum cost from imbalanced fruits
    2m = 1   # number of swaps needed
    3total_cost = min(3, 3 * 2) for the first fruit

    In this case, we choose the fruit's own cost, which is 3, since it's not greater than double the minimum cost fruit.

  7. Return the Minimum Total Cost: The sum is the minimum cost for making both the baskets equal:

    1total_cost = 3

The minimum total cost required to make both baskets contain the same fruits in terms of cost is thus 3. This would involve swapping one of the fruits with cost 3 from basket1 with one of the fruits with cost 4 from basket2.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
5        # Create a counter to track the frequency of each fruit type
6        fruit_counter = Counter()
7      
8        # Iterate over both baskets simultaneously
9        for fruit_type_a, fruit_type_b in zip(basket1, basket2):
10            # Increment the count for fruit type from basket1
11            fruit_counter[fruit_type_a] += 1
12            # Decrement the count for fruit type from basket2
13            fruit_counter[fruit_type_b] -= 1
14      
15        # Get the minimum fruit type value from our counter
16        min_fruit_type = min(fruit_counter)
17      
18        # Prepare a list to count how many exchanges are needed
19        exchange_list = []
20      
21        # Check if exchange is possible given the counts
22        for fruit_type, count in fruit_counter.items():
23            if count % 2:
24                # If count is odd, return -1 (impossible to exchange)
25                return -1
26            # Add the fruit types for exchange to the list
27            exchange_list.extend([fruit_type] * (abs(count) // 2))
28      
29        # Sort the list to facilitate minimum cost calculation
30        exchange_list.sort()
31      
32        # Find the middle point of our sorted list
33        mid_point = len(exchange_list) // 2
34      
35        # Calculate and return the cost of exchanges
36        # By taking minimum exchange cost between the fruit type and double the minimum fruit type
37        return sum(min(fruit_type, min_fruit_type * 2) for fruit_type in exchange_list[:mid_point])
38
1class Solution {
2    public long minCost(int[] basket1, int[] basket2) {
3        int n = basket1.length; // Length of the baskets
4        Map<Integer, Integer> fruitCountMap = new HashMap<>(); // A map to store the count difference of fruits between baskets
5      
6        // Count the difference between the two baskets
7        for (int i = 0; i < n; ++i) {
8            fruitCountMap.merge(basket1[i], 1, Integer::sum);  // Increment count for the current fruit in basket1
9            fruitCountMap.merge(basket2[i], -1, Integer::sum); // Decrement count for the current fruit in basket2
10        }
11      
12        int minFruitValue = Integer.MAX_VALUE; // Initialize the minimum fruit value
13        List<Integer> fruitDifferences = new ArrayList<>(); // List to store absolute differences
14      
15        // Analyze the map to find out the absolute difference and minimum fruit value
16        for (var entry : fruitCountMap.entrySet()) {
17            int fruit = entry.getKey(), count = entry.getValue();
18            if (count % 2 != 0) { // If count is odd, there's no way to balance, return -1
19                return -1;
20            }
21            for (int i = Math.abs(count) / 2; i > 0; --i) {
22                fruitDifferences.add(fruit);  // Add the fruit differences
23            }
24            minFruitValue = Math.min(minFruitValue, fruit); // Update the minimum fruit value if necessary
25        }
26      
27        Collections.sort(fruitDifferences); // Sort the list of differences
28      
29        int m = fruitDifferences.size(); // Size of the list of differences
30        long totalCost = 0; // Initialize the total cost
31      
32        // Calculate the minimum cost of balancing the baskets
33        for (int i = 0; i < m / 2; ++i) {
34            totalCost += Math.min(fruitDifferences.get(i), minFruitValue * 2); // Take the minimum of the current fruit difference and double of min fruit value
35        }
36      
37        return totalCost; // Return the total minimum cost
38    }
39}
40
1class Solution {
2public:
3    // This method calculates the minimum cost to make two baskets identical
4    long long minCost(vector<int>& basket1, vector<int>& basket2) {
5        int n = basket1.size();
6        unordered_map<int, int> countMap; // Map to store the difference in counts of fruits
7
8        // Calculate the count differences for each fruit
9        for (int i = 0; i < n; ++i) {
10            countMap[basket1[i]]++;
11            countMap[basket2[i]]--;
12        }
13
14        int minFruit = INT_MAX; // To store the minimum fruit value encountered
15        vector<int> disparities; // Vector to store fruits which have disparities
16
17        // Loop through the countMap to find disparities
18        for (auto& [fruit, count] : countMap) {
19            // If the count is odd, we cannot make the baskets identical so return -1
20            if (count % 2) {
21                return -1;
22            }
23          
24            // Add the absolute half of the count of each fruit to the disparities vector
25            for (int i = abs(count) / 2; i > 0; --i) {
26                disparities.push_back(fruit);
27            }
28
29            // Update the minimum fruit value
30            minFruit = min(minFruit, fruit);
31        }
32
33        // Sort the disparities vector in ascending order
34        sort(disparities.begin(), disparities.end());
35
36        int m = disparities.size(); // Size of the disparities vector
37        long long totalCost = 0; // To store the total cost required to make the baskets identical
38
39        // Loop to calculate the minimum cost required
40        for (int i = 0; i < m / 2; ++i) {
41            // Cost is the minimum between swapping with the cheapest fruit twice or the current disparity
42            totalCost += min(disparities[i], minFruit * 2);
43        }
44
45        // Return the total cost calculated
46        return totalCost;
47    }
48};
49
1// Importing required collections
2import { HashMap } from "tstl/container/HashMap";
3import { min } from "tstl/algorithm/math";
4
5// This method calculates the minimum cost to make two baskets identical
6function minCost(basket1: number[], basket2: number[]): number {
7    const n: number = basket1.length;
8    const countMap: HashMap<number, number> = new HashMap(); // Map to store the difference in counts of fruits
9
10    // Calculate the count differences for each fruit
11    for (let i = 0; i < n; ++i) {
12        // Increase the count for the current fruit in basket1
13        countMap.set(basket1[i], (countMap.get(basket1[i]) || 0) + 1);
14        // Decrease the count for the current fruit in basket2
15        countMap.set(basket2[i], (countMap.get(basket2[i]) || 0) - 1);
16    }
17
18    let minFruit: number = Number.MAX_VALUE; // To store the minimum fruit value encountered
19    const disparities: number[] = []; // Array to store fruits which have disparities
20
21    // Loop through the countMap to find disparities
22    countMap.forEach((count, fruit) => {
23        // If the count is odd, we cannot make the baskets identical so return -1
24        if (count % 2) {
25            return -1;
26        }
27
28        // Add the absolute half of the count of each fruit to the disparities array
29        for (let i = Math.abs(count) / 2; i > 0; --i) {
30            disparities.push(fruit);
31        }
32
33        // Update the minimum fruit value
34        minFruit = min(minFruit, fruit);
35    });
36
37    // Sort the disparities array in ascending order
38    disparities.sort((a, b) => a - b);
39
40    const m: number = disparities.length; // Size of the disparities array
41    let totalCost: number = 0; // To store the total cost required to make the baskets identical
42
43    // Loop to calculate the minimum cost required
44    for (let i = 0; i < m / 2; ++i) {
45        // Cost is the minimum between swapping with the cheapest fruit twice or the current disparity
46        totalCost += Math.min(disparities[i], minFruit * 2);
47    }
48
49    // Return the total cost calculated
50    return totalCost;
51}
52

Time and Space Complexity

Time Complexity:

The total time complexity of the given Python code is determined by multiple factors:

  1. The loop where we zip basket1 and basket2 and update cnt: this loop runs for every pair of elements in the two lists, so if each list has n elements, this step is O(n).

  2. The min(cnt) operation: finding the minimum in the counter object depends on the number of unique elements in cnt, let's denote this number as k. In the worst case, all elements are unique so k = n. However, typically k is expected to be much less than n. This is a O(k) operation.

  3. The loop to create nums list: the number of iterations is the sum of half the absolute values in cnt (since we're adding abs(v) // 2 elements for each x). In the worst case, this could be O(n) if every swap generates a new unique number in the counter.

  4. The sort() call on nums: if we assume that m is the number of elements in nums, then sorting would take O(m log m). In the worst case, where we have to add n/2 elements to nums, this is O(n log n).

  5. The final loop where we sum the minimum of each element and mi * 2, running m/2 times: this is O(m) which is O(n) in the worst case.

Adding these together, the time complexity is dominated by the sorting operation, resulting in O(n log n).

Space Complexity:

The space complexity is also affected by multiple factors:

  1. The Counter cnt, which has at most k unique elements, where k is the number of unique elements. In the worst case, k = n, so this is O(n).

  2. The nums list, which holds up to n/2 elements in the worst case, making it O(n).

  3. The space required for the output of the min() operation (a single integer) and the final sum operation, both of which are constant, O(1).

Therefore, the combined space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄