[Leetcode] 2561. Rearranging Fruits

https://leetcode.com/problems/rearranging-fruits/solutions/7034081/the-greedy-fruit-swap-a-simple-trick-for-a-hard-problem-python-c-java/

initial

im thinking like counter both lists and counter1-counter2 to subtract the common ones. i sort the remaining keys and if the values are odd number its invalid case so we return -1 but we add value//2 and update value as we iterate through is that valid hmm

but if we subtract counters, like c1-c2, the excess values in c2 do not remain. Instead we should add both counters and if any of the basket has any excess (more than half of the value), then we add that many times of that fruit to another list.

one careful thing is
basket1 = [1,1,4,4], basket2 = [1,1,6,6]
Need to swap: 4 ↔ 6 and cost is mega huge at 4. But we know that if we swap
1 with 4

1,1,1,4
1,4,6,6

and 6 with 1
1,1,6,4
1,4,1,6

so we can use an intermediary minimum value to do a trick.

idk why theres 2 v big input cases that my init code fails

from collections import Counter
class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        counter1=Counter(basket1)
        counter2=Counter(basket2)
        total=counter1+counter2
        b1=[]
        b2=[]
        for key,val in total.items():
            half = val//2
            if val%2==1:
                return -1
            if counter1[key]>half:
                b1.extend((counter1[key]-half)*[key])
            elif counter2[key]>half:
                b2.extend((counter2[key]-half)*[key])
        if len(b1)!=len(b2):
            return -1
        b1.sort()
        b2.sort()
        
        # ADD THIS: Find global minimum
        global_min = min(min(basket1), min(basket2))
        
        ans=0
        for i in range(len(b1)):
            # ADD THIS: Compare direct vs intermediary cost
            direct_cost = min(b1[i], b2[i])
            intermediary_cost = 2 * global_min
            ans += min(direct_cost, intermediary_cost)
        return ans

sol

sol that works

from collections import Counter

class Solution:
    def minCost(self, basket1: list[int], basket2: list[int]) -> int:
        total_counts = Counter(basket1) + Counter(basket2)
        
        for count in total_counts.values():
            if count % 2 != 0:
                return -1
        
        fruits_to_swap = []
        count1 = Counter(basket1)
        for fruit, total_count in total_counts.items():
            target = total_count // 2
            diff = count1.get(fruit, 0) - target
            
            # if diff > 0, b1 has a surplus. if diff < 0, b2 has a surplus.
            # abs(diff) is the number of items of this fruit type in the wrong basket.
            # since each misplaced fruit corresponds to another, we add half.
            for _ in range(abs(diff)):
                fruits_to_swap.append(fruit)

        fruits_to_swap.sort()
        
        min_val = min(total_counts.keys())
        total_cost = 0
        swaps_to_make = len(fruits_to_swap) // 2
        for i in range(swaps_to_make):
            # Cost is min(direct swap cost, helper swap cost)
            total_cost += min(fruits_to_swap[i], 2 * min_val)
            
        return total_cost

complexity

n log n time cuz sort
n space