unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 2561: Rearranging Fruits

link

Observations

  1. By problem constraints, the two baskets have the same number of fruits. As a result, if one fruit type is in excess in basket1, some other fruit types in basket2 will together match that excess.
  2. In the end the two baskets must look the same in sorted order. Therefore, in the end, each type of fruit must appear same number of times in both baskets. In other words, if there is a solution, initially each fruit type must be present even number of times in total – across the two baskets. We use this to confirm a solution exists.
  3. If a fruit type appears n times in excess in basket1, we need to make \frac{n}{2} swaps to distribute it evenly between the two baskets. Since each fruit type had even count to begin with, the excess must also be even. Because sum of two numbers (basket1 count and basket2 count) can be even, only if both numbers are even or both numbers are odd. Difference (excess) of two even numbers or two odd numbers is even.
  4. An excess in a basket makes a swap required. And to minimize swap cost we swap the smallest excess from basket1 with the biggest excess from basket2.
  5. There are two ways we can swap a fruit (say a) from basket1 with a fruit from basket2 (say b). The swap cost will be the minimum of these two:
    • We can directly swap a and b. Swap cost then is min(a, b).
    • We can swap(a, min_cost) and then swap(b, min_cost). Swap cost then is min(a, min_cost) + min(b, min_cost) = 2 * min_cost.

Time: \mathcal{O}(N \cdot \lg{N}), space: \mathcal{O}(N).

from collections import Counter

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        cost_counts = Counter(basket1+basket2)
        if any( (count % 2 == 1 for count in cost_counts.values()) ):
            return -1
        
        basket1_counts = Counter(basket1)
        basket2_counts = Counter(basket2)

        basket1_excess, basket2_excess = [], []
        for cost in cost_counts.keys():
            # If basket1_counts was not initialized with some cost
            # basket1_counts[cost] defauls to 0. As if, dict.get(cost, 0).
            delta = basket1_counts[cost] - basket2_counts[cost]
            if delta == 0: # No swaps needed
                continue
            # Moving half of the excess balances
            # the two baskets for a fruit type
            # So, we need |delta|//2 swaps. 
            repeat_count = abs(delta)//2
            if delta > 0:
                basket1_excess.extend( [cost] * repeat_count )
            else:
                basket2_excess.extend( [cost] * repeat_count )
        
        # Consider swapping biggest cost with smallest cost.
        # That way swap cost, min(biggest_cost, smallest_cost), is minimized.
        basket1_excess.sort()
        basket2_excess.sort(reverse=True)

        # We can swap a and b through min_element
        # swap(a, min_element), swap(b, min_element)
        indirect_swap_cost = 2*min(cost_counts.keys())
        
        total_cost = 0
        # This loop iterates through every required swap.
        # Since the two baskets have the same length (constraints)
        # the excesses must have same length as well. 
        for cost1, cost2 in zip(basket1_excess, basket2_excess, strict=True):
            direct_swap_cost = min(cost1, cost2)
            total_cost += min( direct_swap_cost, indirect_swap_cost )

        return total_cost

tanvirdotzaman

Leave a comment