LeetCode 888: Fair Candy Swap

Problem Restatement

Alice and Bob each have several candy boxes.

aliceSizes[i] is the number of candies in Alice’s ith box.

bobSizes[j] is the number of candies in Bob’s jth box.

They want to exchange exactly one box each so that after the swap, they have the same total number of candies.

Return:

[alice_box, bob_box]

where alice_box is the size of the box Alice gives to Bob, and bob_box is the size of the box Bob gives to Alice.

If there are multiple valid answers, we may return any one of them. The problem guarantees that at least one valid answer exists. LeetCode states these arrays as aliceSizes and bobSizes, and asks for one valid swap.

Input and Output

Function shape:

def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
    ...

Examples

Example 1:

Input: aliceSizes = [1,1], bobSizes = [2,2]
Output: [1,2]

Alice starts with:

1 + 1 = 2

Bob starts with:

2 + 2 = 4

If Alice gives 1 and Bob gives 2, then Alice has:

2 - 1 + 2 = 3

Bob has:

4 - 2 + 1 = 3

Both have 3, so [1, 2] is valid.

Example 2:

Input: aliceSizes = [1,2], bobSizes = [2,3]
Output: [1,2]

Alice starts with 3.

Bob starts with 5.

Swap Alice’s 1 with Bob’s 2:

Alice: 3 - 1 + 2 = 4
Bob:   5 - 2 + 1 = 4

So the answer is [1, 2].

Example 3:

Input: aliceSizes = [2], bobSizes = [1,3]
Output: [2,3]

Alice starts with 2.

Bob starts with 4.

Swap 2 and 3:

Alice: 2 - 2 + 3 = 3
Bob:   4 - 3 + 2 = 3

So the answer is [2, 3].

First Thought: Try Every Pair

A direct approach is to try every box from Alice and every box from Bob.

For each pair (x, y), check whether swapping them makes the totals equal.

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sum_alice = sum(aliceSizes)
        sum_bob = sum(bobSizes)

        for x in aliceSizes:
            for y in bobSizes:
                if sum_alice - x + y == sum_bob - y + x:
                    return [x, y]

        return []

This is correct, but it may be slow.

If both arrays have many boxes, this checks too many pairs.

Problem With Brute Force

Let:

A = len(aliceSizes)
B = len(bobSizes)

The brute force approach checks:

A * B

pairs.

The constraints allow both arrays to be large, so we need a faster way.

Key Insight

Let:

sumA = sum(aliceSizes)
sumB = sum(bobSizes)

Suppose Alice gives a box of size x, and Bob gives a box of size y.

After the swap:

Alice has sumA - x + y
Bob has   sumB - y + x

We need:

sumA - x + y = sumB - y + x

Rearrange:

2y = sumB - sumA + 2x

So:

y = x + (sumB - sumA) / 2

That means for each Alice box x, we know exactly what Bob box y is needed.

So we can store Bob’s box sizes in a set and check quickly.

Algorithm

Compute:

sum_alice = sum(aliceSizes)
sum_bob = sum(bobSizes)

The amount Bob’s box must exceed Alice’s box by is:

delta = (sum_bob - sum_alice) // 2

For each x in aliceSizes, we need:

y = x + delta

If y exists in Bob’s set, return:

[x, y]

Walkthrough

Use:

aliceSizes = [1, 2]
bobSizes = [2, 3]

Compute sums:

Bob has 2 more candies than Alice.

After one swap, the difference must be removed from both sides. So Bob needs to give Alice a box that is larger by:

(5 - 3) / 2 = 1

So for Alice’s box x, Bob’s needed box is:

x + 1

Try Alice’s box 1:

needed Bob box = 1 + 1 = 2

Bob has a box of size 2.

Return:

[1, 2]

Correctness

Let sumA be Alice’s original total and sumB be Bob’s original total.

Suppose the algorithm returns [x, y].

The algorithm only returns such a pair when x is in aliceSizes, y is in bobSizes, and:

y = x + (sumB - sumA) / 2

Then:

2(y - x) = sumB - sumA

Rearranging gives:

sumA - x + y = sumB - y + x

So after the swap, Alice and Bob have equal totals. Therefore, the returned pair is valid.

Now suppose a valid answer exists, as guaranteed by the problem. Let that answer be [x, y].

Because the swap is valid:

sumA - x + y = sumB - y + x

Rearranging gives:

y = x + (sumB - sumA) / 2

When the algorithm checks this Alice box x, it computes exactly this required y. Since y is one of Bob’s boxes, it will be found in the set, and the algorithm will return a valid answer.

Thus, the algorithm always returns a correct swap.

Complexity

Let:

A = len(aliceSizes)
B = len(bobSizes)

Implementation

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sum_alice = sum(aliceSizes)
        sum_bob = sum(bobSizes)

        delta = (sum_bob - sum_alice) // 2
        bob_set = set(bobSizes)

        for x in aliceSizes:
            y = x + delta

            if y in bob_set:
                return [x, y]

        return []

Code Explanation

We first compute both totals:

sum_alice = sum(aliceSizes)
sum_bob = sum(bobSizes)

Then compute how much larger Bob’s chosen box must be than Alice’s chosen box:

delta = (sum_bob - sum_alice) // 2

We store Bob’s box sizes in a set:

bob_set = set(bobSizes)

This lets us check whether a needed box size exists in expected O(1) time.

For each Alice box:

for x in aliceSizes:

the needed Bob box is:

y = x + delta

If Bob has that box, we return the swap:

if y in bob_set:
    return [x, y]

The final return is only a fallback. The problem guarantees that a valid answer exists.

Testing

def run_tests():
    s = Solution()

    assert s.fairCandySwap([1, 1], [2, 2]) == [1, 2]
    assert s.fairCandySwap([1, 2], [2, 3]) == [1, 2]
    assert s.fairCandySwap([2], [1, 3]) == [2, 3]
    assert s.fairCandySwap([1, 2, 5], [2, 4]) == [5, 4]

    result = s.fairCandySwap([8, 4], [1, 2, 3, 7])
    x, y = result
    assert sum([8, 4]) - x + y == sum([1, 2, 3, 7]) - y + x

    print("all tests passed")

run_tests()

Test meaning: