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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rearranging Fruits

Number: 2689

Difficulty: Hard

Paid? No

Companies: Oracle

Problem Description

You are given two baskets (basket1 and basket2) containing n fruits each, where each fruit is represented by its cost. You can perform swap operations between any fruit from basket1 with any fruit from basket2. The cost of a swap is the minimum of the two fruit costs being swapped. The goal is to make the two baskets "equal" (i.e. after sorting both baskets, they should be identical) at a minimum total cost. If it is impossible to achieve, return -1.

Key Insights

  • The total frequency (combined from both baskets) of each fruit must be even; otherwise, it is impossible to split evenly.
  • Calculate the surplus fruits from one basket that need to be swapped out to balance both baskets.
  • Use sorting to pair the smallest surplus fruit from one basket with the largest surplus fruit from the other, ensuring optimal swap costs.
  • There is a trick: instead of directly swapping two fruits, sometimes it is cheaper to perform two swaps involving the smallest fruit overall (global minimum). Thus, for each swap pair, the effective cost is the minimum between:
    • The direct swap cost, min(x, y)
    • Indirect cost using the smallest fruit globally, which is 2 * globalMin

Space and Time Complexity

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

Solution

The solution begins by verifying if the transformation is possible. We combine the two baskets and count the frequencies. If any fruit has an odd combined frequency, the answer is -1. Next, we compute how many extra fruits each basket has (over the desired equal split) using frequency counts. We then sort the extra fruits from basket1 in ascending order and those from basket2 in descending order. For each pair of surplus fruits, we calculate the cost as the minimum between a direct swap (min(value1, value2)) and two swaps via the basket’s global minimum (2 * globalMin). The total cost accumulated is the minimal cost required to balance the baskets.

Code Solutions

Below are sample implementations in Python, JavaScript, C++, and Java.

# Python solution for "Rearranging Fruits"
from collections import Counter

def min_cost_to_make_baskets_equal(basket1, basket2):
    # Combine both baskets and obtain the global frequency count.
    combined = basket1 + basket2
    freq = Counter(combined)
    
    # If any fruit appears an odd number of times, we cannot split it equally.
    for fruit, count in freq.items():
        if count % 2 != 0:
            return -1
    
    # Frequency count for basket1.
    count1 = Counter(basket1)
    extra_basket1 = []
    # Global minimum fruit cost for potential indirect swap.
    global_min = min(combined)
    
    # Determine extra fruits in basket1 that exceed the half of total occurrences.
    for fruit in freq:
        desired = freq[fruit] // 2
        if count1[fruit] > desired:
            extra_basket1.extend([fruit] * (count1[fruit] - desired))
    
    # Sort the extra fruits in basket1 in ascending order.
    extra_basket1.sort()
    
    # For basket2, extra fruits that need to be swapped out.
    count2 = Counter(basket2)
    extra_basket2 = []
    for fruit in freq:
        desired = freq[fruit] // 2
        if count2[fruit] > desired:
            extra_basket2.extend([fruit] * (count2[fruit] - desired))
    
    # Sort extra fruits of basket2 in descending order.
    extra_basket2.sort(reverse=True)
    
    total_cost = 0
    # Iterate through each pair of extra fruits to calculate swap cost.
    for i in range(len(extra_basket1)):
        direct_swap_cost = min(extra_basket1[i], extra_basket2[i])
        # Indirect swap using the global minimum fruit appears as 2 * global_min.
        total_cost += min(direct_swap_cost, 2 * global_min)
    
    return total_cost

# Example usage:
# basket1 = [4,2,2,2]
# basket2 = [1,4,1,2]
# print(min_cost_to_make_baskets_equal(basket1, basket2))
← Back to All Questions