We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rearranging Fruits

Difficulty: Hard

Problem Description

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: Choose 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.

Key Insights

  • Both baskets need to have the same fruit costs for them to be made equal.
  • Count the frequency of each fruit cost in both baskets.
  • Any excess fruit costs in one basket must be balanced by the other.
  • Swapping costs depend on the minimum fruit cost being swapped.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a frequency map (or hash table) to count the occurrences of each fruit cost in both baskets. The key steps are as follows:

  1. Calculate the frequency of each fruit cost in both baskets.
  2. Determine if the excess fruit costs in one basket can be matched by the other basket.
  3. If they can be matched, calculate the minimum cost of swaps required to equalize the baskets, using the minimum cost fruit from either basket for optimization.

Code Solutions

from collections import Counter

def minCost(basket1, basket2):
    count1 = Counter(basket1)
    count2 = Counter(basket2)

    # Check if both baskets can be made equal
    for fruit in count1:
        if count1[fruit] > count2[fruit]:
            if (count1[fruit] - count2[fruit]) % 2 != 0:
                return -1
    for fruit in count2:
        if count2[fruit] > count1[fruit]:
            if (count2[fruit] - count1[fruit]) % 2 != 0:
                return -1

    # Calculate the minimum cost
    excess1 = []
    excess2 = []
    min_cost = min(min(basket1), min(basket2))

    for fruit in count1:
        if count1[fruit] > count2[fruit]:
            excess1.extend([fruit] * ((count1[fruit] - count2[fruit]) // 2))
    for fruit in count2:
        if count2[fruit] > count1[fruit]:
            excess2.extend([fruit] * ((count2[fruit] - count1[fruit]) // 2))

    total_cost = 0
    for fruit in excess1:
        total_cost += min(fruit, min_cost)

    return total_cost
← Back to All Questions