LeetCode 888 - Fair Candy Swap

The problem gives us two arrays, aliceSizes and bobSizes, representing the candy boxes owned by Alice and Bob. Each element in the arrays is the number of candies in a particular box.

leetcodeeasyarrayhash-tablebinary-searchsorting

LeetCode Problem 888

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Binary Search, Sorting

Solution

LeetCode 888 - Fair Candy Swap

Problem Understanding

The problem gives us two arrays, aliceSizes and bobSizes, representing the candy boxes owned by Alice and Bob. Each element in the arrays is the number of candies in a particular box.

Alice and Bob want to exchange exactly one box each so that, after the swap, the total number of candies they each own becomes equal.

We need to return a pair of integers:

  • answer[0] is the candy box Alice gives away
  • answer[1] is the candy box Bob gives away

The problem guarantees that at least one valid solution exists.

To understand the problem more clearly, suppose:

  • Alice currently has total candy count sumAlice
  • Bob currently has total candy count sumBob

If Alice gives away a box with a candies and receives a box with b candies, then:

  • Alice's new total becomes sumAlice - a + b
  • Bob's new total becomes sumBob - b + a

We want these totals to be equal.

The input constraints are important:

  • Each array can contain up to 10^4 elements
  • Candy counts can be as large as 10^5

These constraints are large enough that a quadratic solution may become too slow in practice, especially if both arrays contain 10^4 elements. A solution close to linear time is preferable.

The problem also guarantees:

  • Alice and Bob initially have different total candy counts
  • A valid answer always exists

This guarantee simplifies implementation because we do not need to handle failure cases.

Some important edge cases include:

  • Arrays of length 1
  • Large differences between totals
  • Duplicate candy box sizes
  • Multiple valid answers
  • Cases where the matching swap involves the largest or smallest values

A naive implementation could become inefficient if it compares every possible pair of boxes.

Approaches

Brute Force Approach

The most direct approach is to try every possible swap.

For every candy box a in Alice's collection, we try every candy box b in Bob's collection. After simulating the swap, we check whether both totals become equal.

The condition is:

sumAlice - a + b == sumBob - b + a

If the condition holds, we return [a, b].

This approach is guaranteed to work because it exhaustively checks all possible swaps.

However, if Alice and Bob each have 10^4 boxes, then we may perform:

10^4 × 10^4 = 10^8

comparisons.

That is too slow for an efficient solution.

Optimal Approach

The key insight comes from simplifying the equality equation.

We start with:

sumAlice - a + b = sumBob - b + a

Rearranging terms:

sumAlice - sumBob = 2a - 2b

Divide both sides by 2:

a - b = (sumAlice - sumBob) / 2

This equation tells us exactly what relationship must exist between the swapped boxes.

If we define:

difference = (sumAlice - sumBob) // 2

then:

b = a - difference

Now the problem becomes:

For each a in Alice's array, check whether Bob owns a box equal to:

a - difference

This is an ideal use case for a hash set because membership checks are O(1) on average.

We store all of Bob's candy box sizes in a set, then iterate through Alice's boxes and search for the required matching value.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m) O(1) Tries every possible pair of swaps
Optimal O(n + m) O(m) Uses algebra and a hash set for fast lookup

Algorithm Walkthrough

  1. Compute the total number of candies owned by Alice and Bob.

We calculate:

sumAlice = sum(aliceSizes)
sumBob = sum(bobSizes)

These totals determine how unbalanced the candy distribution currently is. 2. Compute the required difference.

From the derived equation:

a - b = (sumAlice - sumBob) / 2

we compute:

difference = (sumAlice - sumBob) // 2

This tells us exactly how much larger Alice's exchanged box must be compared to Bob's. 3. Store Bob's candy sizes in a hash set.

We create:

bobSet = set(bobSizes)

A hash set allows constant time membership checks. 4. Iterate through Alice's candy boxes.

For each candy box a, we compute the box Bob must provide:

target = a - difference
  1. Check whether Bob owns the required box.

If target exists in bobSet, then swapping a and target equalizes the totals. 6. Return the valid pair.

Since the problem guarantees a valid answer exists, the first valid pair can be returned immediately.

Why it works

The algorithm is correct because it directly derives the exact mathematical condition required for equal totals after the swap.

The equation:

a - b = (sumAlice - sumBob) / 2

fully characterizes every valid swap. By searching for a matching b value for each a, we are guaranteed to find a correct solution if one exists.

The hash set ensures this search is efficient.

Python Solution

from typing import List

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

        difference = (sum_alice - sum_bob) // 2

        bob_set = set(bobSizes)

        for alice_box in aliceSizes:
            target = alice_box - difference

            if target in bob_set:
                return [alice_box, target]

        return []

The implementation begins by computing the total candies owned by Alice and Bob. These totals are required to derive the swap condition mathematically.

Next, the code computes the required difference between the exchanged boxes. This value represents how much larger Alice's exchanged box must be.

The solution then converts Bob's candy sizes into a set. This is a critical optimization because set membership checks are extremely fast compared to searching through a list.

The algorithm iterates through each candy box Alice owns. For every box, it calculates the exact candy count Bob must provide in return.

If Bob owns such a box, the pair is immediately returned.

The final return [] statement is technically unnecessary because the problem guarantees a solution exists, but including it makes the function syntactically complete.

Go Solution

func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
    sumAlice := 0
    sumBob := 0

    for _, value := range aliceSizes {
        sumAlice += value
    }

    for _, value := range bobSizes {
        sumBob += value
    }

    difference := (sumAlice - sumBob) / 2

    bobSet := make(map[int]bool)

    for _, value := range bobSizes {
        bobSet[value] = true
    }

    for _, aliceBox := range aliceSizes {
        target := aliceBox - difference

        if bobSet[target] {
            return []int{aliceBox, target}
        }
    }

    return []int{}
}

The Go implementation follows the same logic as the Python version.

Because Go does not have a built in set type, a map[int]bool is used to simulate a hash set.

Integer arithmetic is safe here because the maximum possible total candy count is well within Go's integer range.

The function returns an empty slice at the end for completeness, even though the problem guarantees a valid answer exists.

Worked Examples

Example 1

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

Step 1: Compute totals

Variable Value
sumAlice 2
sumBob 4

Step 2: Compute difference

difference = (2 - 4) // 2
           = -1

Step 3: Build Bob's set

bobSet = {2}

Step 4: Iterate through Alice's boxes

aliceBox target = aliceBox - difference Exists in bobSet?
1 2 Yes

Return:

[1, 2]

Example 2

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

Step 1: Compute totals

Variable Value
sumAlice 3
sumBob 5

Step 2: Compute difference

difference = (3 - 5) // 2
           = -1

Step 3: Build Bob's set

bobSet = {2, 3}

Step 4: Iterate through Alice's boxes

aliceBox target Exists?
1 2 Yes

Return:

[1, 2]

Example 3

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

Step 1: Compute totals

Variable Value
sumAlice 2
sumBob 4

Step 2: Compute difference

difference = (2 - 4) // 2
           = -1

Step 3: Build Bob's set

bobSet = {1, 3}

Step 4: Iterate through Alice's boxes

aliceBox target Exists?
2 3 Yes

Return:

[2, 3]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) One pass for sums, one pass to build the set, one pass to search
Space O(m) The hash set stores Bob's candy sizes

The algorithm is linear with respect to the size of the input arrays.

The dominant operations are:

  • Summing the arrays
  • Building the hash set
  • Iterating through Alice's array once

Hash set lookups are constant time on average, which keeps the overall complexity efficient.

Test Cases

from typing import List

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

        difference = (sum_alice - sum_bob) // 2

        bob_set = set(bobSizes)

        for alice_box in aliceSizes:
            target = alice_box - difference

            if target in bob_set:
                return [alice_box, target]

        return []

solution = Solution()

assert solution.fairCandySwap([1, 1], [2, 2]) == [1, 2]  # basic example
assert solution.fairCandySwap([1, 2], [2, 3]) == [1, 2]  # different totals
assert solution.fairCandySwap([2], [1, 3]) == [2, 3]  # single-element array

result = solution.fairCandySwap([1, 2, 5], [2, 4])
assert result == [5, 4]  # larger adjustment required

result = solution.fairCandySwap([10, 20], [5, 15])
assert result == [20, 15]  # larger values

result = solution.fairCandySwap([1, 1, 1, 8], [2, 2, 6])
assert result == [8, 6]  # duplicate values

result = solution.fairCandySwap([100000], [99999, 1])
assert result == [100000, 99999]  # large candy counts

result = solution.fairCandySwap([3, 6, 9], [4, 7, 8])
assert result == [6, 7]  # balanced through middle values

Test Summary

Test Why
[1,1] and [2,2] Basic provided example
[1,2] and [2,3] Simple unequal totals
[2] and [1,3] Minimum array size
[1,2,5] and [2,4] Requires larger correction
[10,20] and [5,15] Tests larger values
[1,1,1,8] and [2,2,6] Tests duplicate elements
[100000] and [99999,1] Tests upper candy limits
[3,6,9] and [4,7,8] Tests mid-array matching

Edge Cases

One important edge case is when the arrays contain only one element each. In such cases, the algorithm must still correctly compute the totals and identify the only possible swap. Because the solution uses the same mathematical derivation regardless of array size, it handles this case naturally without any special logic.

Another important edge case involves duplicate candy box sizes. For example, Bob may own several boxes with the same candy count. A naive implementation might accidentally perform redundant work or incorrectly track indices. The hash set based solution avoids this issue entirely because it only needs to know whether a valid candy count exists, not how many times it appears.

Large candy counts are also important to consider. Since values can reach 10^5, total sums can become fairly large. However, the maximum possible total remains well within standard integer limits in both Python and Go. The implementation safely handles these values using normal integer arithmetic.

A final edge case occurs when multiple valid answers exist. The problem explicitly allows returning any valid pair. The implementation returns the first valid match it encounters during iteration, which satisfies the requirements without additional complexity.