Fair Candy Swap: Hash Set Lookup

May 24, 20264 min read

leetcodeproblemeasyarrayshash-mapsorting

LeetCode 888. Fair Candy Swap gives you two integer arrays, aliceSizes and bobSizes, representing the sizes of candy bars that Alice and Bob have. They want to swap exactly one bar each so that after the swap, both have the same total candy. You need to return the pair [a, b] where a is the size Alice gives and b is the size Bob gives.

The problem guarantees that at least one valid swap exists.

Alice has [1, 2, 5] (sum 8) and Bob has [2, 4] (sum 6). Swapping Alice's 5 for Bob's 4 gives both a total of 7.

Why does one swap always exist?

A little algebra makes this click. Let sumA be Alice's total and sumB be Bob's total. After swapping bar a from Alice for bar b from Bob, Alice's new total is sumA - a + b and Bob's new total is sumB - b + a. For these to be equal:

sumA - a + b = sumB - b + a

Rearranging:

2b = 2a + sumB - sumA
b  = a + (sumB - sumA) / 2

Call (sumB - sumA) / 2 the delta. For every candy bar a that Alice has, the matching bar from Bob must be exactly a + delta. The problem guarantees that the total sum sumA + sumB is even after the swap, so delta is always an integer.

This means you do not need to try every pair. You just need to find one value a in Alice's array such that a + delta exists in Bob's array.

Approach: hash set lookup

The plan is simple. Compute both sums, compute the delta, then build a set from Bob's sizes. Scan through Alice's sizes and check whether a + delta is in Bob's set. The first match gives you the answer.

def fair_candy_swap(aliceSizes, bobSizes):
    sumA = sum(aliceSizes)
    sumB = sum(bobSizes)
    delta = (sumB - sumA) // 2
    bobSet = set(bobSizes)
    for a in aliceSizes:
        b = a + delta
        if b in bobSet:
            return [a, b]

This is the same complement lookup pattern you use in Two Sum. Instead of looking for target - num, you look for a + delta. The set gives you O(1) lookups, so the whole thing runs in linear time.

Practice the hash set lookup pattern

Step-by-step walkthrough

Step 1: Compute totals

Alice's total is 2, Bob's total is 4. They need to be equal after a one-for-one swap.

Step 2: Compute the delta

delta =(sumB - sumA) // 2 = (4 - 2) // 2 = 1

We need:b = a + 1

The delta tells us how much larger the swapped-in value must be compared to the swapped-out value. For every candidate a from Alice, the matching b is a + delta.

Step 3: Build a set from Bob's sizes

bobSet ={2}

Store Bob's candy sizes in a set so we can check membership in O(1). Since both of Bob's bars are size 2, the set has just one entry.

Step 4: Scan Alice's sizes for a match

For a = 1, we check: is 1 + 1 = 2 in bobSet? Yes! Return [1, 2]. Alice gives a bar of size 1, Bob gives a bar of size 2.

The walkthrough uses aliceSizes = [1, 1] and bobSizes = [2, 2]. Alice's total is 2, Bob's total is 4, so the delta is 1. On the very first element, a = 1 and b = 1 + 1 = 2, which exists in Bob's set. The answer is [1, 2].

Complexity analysis

Approach	Time	Space
Hash set	O(n + m)	O(m) for the set
Sorting + two pointers	O(n log n + m log m)	O(1) extra

The hash set approach is optimal for time. You iterate through both arrays once (O(n + m)) and the set uses O(m) space. The sorting approach avoids extra space but pays for it with the sort cost.

If an interviewer asks you to optimize for space, mention the sorting + two pointers approach. Sort both arrays, then use two pointers that walk forward through both. If the current pair's difference is too small, advance the pointer in Alice's array. If too large, advance Bob's. This works because sorting preserves the delta relationship.

Try both approaches on CodeBricks

Building blocks

1. Hash set complement lookup

This is the same "seen set" technique from Two Sum. You precompute a target value for each element, then check whether that target exists in a set. The only difference between problems is how you compute the complement:

Two Sum: complement = target - num
Fair Candy Swap: complement = a + delta
Two Sum II (sorted): use two pointers instead of a set, same idea

Any time you need to find a pair across two collections (or within one collection) that satisfies some arithmetic relationship, the complement lookup pattern applies.

2. Sum and offset arithmetic

Before you can do the lookup, you need to derive the right offset. The key step is the algebra: rearranging the equality constraint to express b in terms of a and a constant. This "compute a delta from the totals" technique shows up whenever you need to balance two quantities. The formula delta = (sumB - sumA) // 2 is specific to this problem, but the process of deriving it is reusable.

Edge cases

Minimum-size arrays: When one array has a single element, there is only one candidate for a. The algorithm checks it immediately. No special case needed.
Identical arrays: If both arrays are the same (like [1, 2, 3] and [1, 2, 3]), delta = 0, and you need to find any value that appears in both. The set intersection handles this naturally.
Large values with small delta: The delta can be zero even when the arrays look very different, as long as the sums match. Your set lookup handles this without any special case.

From understanding to recall

Fair Candy Swap is an easy problem, but it tests whether you can derive a formula from a constraint and then implement the complement lookup pattern cleanly. These are two separate skills, and they come apart under time pressure if you have not practiced them individually.

CodeBricks breaks this problem into its building blocks and drills them with spaced repetition. You practice the delta derivation and the set lookup as separate cards, then combine them when they come up together. After a few review cycles, the pattern fires automatically when you see a "balance two quantities" problem.

Start drilling with CodeBricks

Two Sum - The classic hash set complement lookup
Contains Duplicate - Another hash set membership problem