Question

Intuition

Using binary search

Approach

Complexity

• Time complexity: $$O((m+n)\ log\ n)$$

• Space complexity: $$O(1)$$ (sorting in-place and ignoring the sort's stack space)

Code

class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        aliceTotal, bobTotal = sum(aliceSizes), sum(bobSizes)
        bobSizes.sort()
        for aSize in aliceSizes:
            requiredBSize = (bobTotal - aliceTotal + 2 * aSize) // 2
            low, high = 0, len(bobSizes) - 1
            while low <= high:
                mid = (low + high) // 2
                if bobSizes[mid] == requiredBSize:
                    return [aSize, requiredBSize]
                elif bobSizes[mid] < requiredBSize:
                    low = mid + 1
                else:
                    high = mid - 1
        

Result