Fair Candy Swap (LeetCode 888): One Equation and a Hash Set
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.
Comments