#888

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Fair Candy Swap

Determine which single candy box Alice and Bob should swap to equalize their total candies using array scanning and hash lookup.

array hash table binary search sorting

Problem Statement

Alice and Bob each have several boxes of candies represented as integer arrays aliceSizes and bobSizes, where each element denotes the number of candies in a box. The total candies for Alice and Bob differ, and they want to swap exactly one box each to balance their totals.

Return an array answer where answer[0] is the number of candies in the box Alice should give, and answer[1] is the number of candies in the box Bob should give. Multiple valid answers may exist, but at least one guaranteed solution exists for every input.

Examples

Example 1

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

Output: [1,2]

Example details omitted.

Example 2

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

Output: [1,2]

Example details omitted.

Example 3

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

Output: [2,3]

Example details omitted.

Constraints

1 <= aliceSizes.length, bobSizes.length <= 104
1 <= aliceSizes[i], bobSizes[j] <= 105
Alice and Bob have a different total number of candies.
There will be at least one valid answer for the given input.

Solution Approach

Calculate total sums and target difference

Compute the sum of candies for Alice and Bob. The difference between their totals divided by two identifies the required delta for a fair swap. This delta guides which pairs to check and eliminates unnecessary comparisons.

Use hash set for constant-time lookup

Store all Bob's candy box sizes in a hash set. For each Alice box, check if adding the delta equals any value in Bob's set. This avoids O(n*m) scans and leverages the hash table to find a valid swap efficiently.

Return the first valid swap found

Iterate through Alice's boxes and use the hash set check. Once a matching Bob box is identified, return the pair immediately. The guarantee of a solution ensures that this first match is valid, maintaining linear time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) due to summing arrays and iterating once over Alice's boxes with constant-time hash lookups. Space complexity is O(m) to store Bob's boxes in a hash set for fast membership checking.

What Interviewers Usually Probe

Checks if you recognize the pattern of array scanning plus hash lookup.
Tests whether you handle differences in total sums correctly.
Looks for use of constant-time data structures to avoid nested loops.

Common Pitfalls or Variants

Common pitfalls

Trying nested loops without using hash set, resulting in O(n*m) complexity.
Miscomputing the delta by not dividing the total difference by 2.
Returning invalid pairs or assuming multiple swaps are needed instead of exactly one.

Follow-up variants

Swapping multiple boxes to balance totals instead of just one.
Allowing unequal exchanges but minimizing difference after swap.
Input arrays with duplicate candy counts requiring handling in the hash set.

FAQ

What is the core pattern used in Fair Candy Swap?

The problem uses array scanning combined with hash lookup to identify a pair of boxes whose swap equalizes totals.

Why do we divide the total difference by two?

Dividing by two calculates the exact delta that each swap must correct to balance Alice's and Bob's totals.

Can there be multiple valid answers?

Yes, multiple valid swaps can exist, and any one can be returned because at least one solution is guaranteed.

What if arrays contain duplicates?

Duplicates are handled naturally since the hash set stores distinct Bob box values, ensuring the correct match is found.

What is the time complexity using the hash lookup approach?

The approach runs in O(n + m) time, iterating over Alice's array and using constant-time lookups in Bob's hash set.

terminal

Solution

Solution 1: Hash Table

We can first calculate the difference in the total number of candies between Alice and Bob, divide it by two to get the difference in the number of candies to be exchanged $\textit{diff}$, and use a hash table $\textit{s}$ to store the number of candies in Bob's candy boxes. Then, we traverse Alice's candy boxes, and for each candy count $\textit{a}$, we check if $\textit{a} - \textit{diff}$ is in the hash table $\textit{s}$. If it exists, it means we have found a valid answer, and we return it.

1

2

3

4

5

6

7

class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        diff = (sum(aliceSizes) - sum(bobSizes)) >> 1
        s = set(bobSizes)
        for a in aliceSizes:
            if (b := (a - diff)) in s:
                return [a, b]

Continue Practicing

#792 number of matching subsequences #710 random pick with blacklist #1170 compare strings by frequency of the smallest character