top of page

Fair Candy Swap (LeetCode 888): One Equation and a Hash Set

Nov 3
1 min read

Alice and Bob each have boxes of candy with different totals. They want to swap exactly one box each so their totals become equal. The problem guarantees an answer exists.

Turn it into algebra

Let the sums be A and B. If Alice gives x and receives y, then A - x + y = B - y + x, which simplifies to y = x + (B - A) / 2. So for each box x that Alice owns, you only need to know whether Bob owns the box x + delta, where delta = (B - A) / 2.

Code

def fair_candy_swap(alice, bob):
    delta = (sum(bob) - sum(alice)) // 2
    bob_set = set(bob)
    for x in alice:
        if x + delta in bob_set:
            return [x, x + delta]

print(fair_candy_swap([1, 2], [2, 3]))  # [1, 2]

Building the set is O(m) and the scan is O(n), so the total is O(m + n) time and O(m) space, compared with O(m*n) for trying every pair.

What to say in the interview

Derive the equation out loud before coding; it shows you look for structure instead of brute-forcing. Mention that delta is always an integer here because a valid swap is guaranteed, and that sorting plus two pointers is an O(1) extra-space alternative.

Disclosure: I'm on the Linkjob AI team, which builds a real-time AI interview helper for practicing explanations like this during mock interviews.

 
 
 

Recent Posts

See All
Image Smoother (LeetCode 661): Clean Neighbor Loops

For each cell of a grayscale image, replace it with the floor of the average of itself and its up to eight neighbors. Idea Loop over the 3x3 block around each cell, skip coordinates outside the grid,

 
 
 

Comments


bottom of page