Fair Candy Swap - Solution & Explanation
Problem Statement
Alice and Bob have a different total number of candies. You are given two integer arrays aliceSizes and bobSizes where aliceSizes[i] is the number of candies of the ith box of candy that Alice has and bobSizes[j] is the number of candies of the jth box of candy that Bob has.
Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.
Return an integer array answer where answer[0] is the number of candies in the box that Alice must exchange, and answer[1] is the number of candies in the box that Bob must exchange. If there are multiple answers, you may return any one of them. It is guaranteed that at least one answer exists.
Example 1:
Input: aliceSizes = [1,1], bobSizes = [2,2] Output: [1,2]
Example 2:
Input: aliceSizes = [1,2], bobSizes = [2,3] Output: [1,2]
Example 3:
Input: aliceSizes = [2], bobSizes = [1,3] Output: [2,3]
Constraints:
1 <= aliceSizes.length, bobSizes.length <= 1041 <= 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.
Approach Overview
Problem Overview: Alice and Bob each have candy bars represented by arrays. They want to exchange exactly one bar each so the total candy they own becomes equal. The task is to return the pair of values that makes the totals balanced after the swap.
Approach 1: Calculating Based on Difference (Hash Set) (Time: O(n + m), Space: O(n))
Start by computing the total candies for Alice and Bob. If Alice gives a and Bob gives b, the new totals become equal when a - b = (sumA - sumB) / 2. This transforms the problem into finding a pair where the difference matches this value. Store Bob's candy sizes in a hash set for constant-time lookup. Iterate through Alice's candies, compute the required b, and check if it exists in the set. The constant-time membership check makes the overall complexity linear.
This approach is the most common interview solution because it combines arithmetic insight with efficient lookups using a hash table. It works well even when the arrays are unsorted and avoids unnecessary comparisons.
Approach 2: Sorting and Two-Pointer Technique (Time: O(n log n + m log m), Space: O(1) or O(log n))
Another option is to sort both arrays and search for the correct pair using two pointers. After computing the required difference target = (sumA - sumB) / 2, you want values where a - b = target. Sort both arrays using a standard sorting algorithm. Place one pointer at the start of Alice's array and another at the start of Bob's array. Compare a - b with the target. Move the pointer that helps move the difference toward the target value.
The sorted structure guarantees progress toward the correct pair without checking every combination. The tradeoff is the sorting cost, which increases the time complexity compared to the hash-based method.
This technique relies on ordered traversal and pointer adjustments, a common pattern when working with sorted arrays. It is useful when hash tables are restricted or when the arrays are already sorted.
Recommended for interviews: The hash-set difference approach is usually expected. It runs in linear time and demonstrates that you recognized the key mathematical insight behind the swap condition. Mentioning the sorting + two-pointer alternative shows broader problem-solving ability, but the O(n) hash approach signals stronger optimization skills.
Approach 1: Approach 1: Calculating based on difference
In this approach, we first calculate the total number of candies Alice and Bob have, respectively. Let this be sumA for Alice and sumB for Bob. If Alice swaps a candy box with x candies and Bob swaps a box with y candies, the condition to balance their total candies after swap can be derived as: sumA - x + y = sumB - y + x. Simplifying this, we get y = x + (sumB - sumA) / 2. Using this equation, we can loop through one person's candy sizes array and for each candy size, compute the necessary size from the other person's array and check if it exists using a set for quick lookup.
The C code initializes the required sums for Alice and Bob. Then it computes the difference in candies needed (delta) and uses an array to act as a set for Bob's candy sizes. Finally, it attempts to find a suitable swap by iterating over Alice's candy sizes and checking if Bob has the necessary candy size using the array.
Complexity
Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes. This is because we iterate over each list once and use constant time checks for the existence of an element in Bob's collection.
Space Complexity: O(m), due to the additional space used for storing Bob's candy sizes in a set.
Approach 2: Approach 2: Sorting and Two-Pointer Technique
This approach involves first sorting both the candy size arrays of Alice and Bob. The idea is to use a two-pointer technique to find a suitable pair of candy boxes such that swapping them would balance Alice's and Bob's total candies. Once both lists are sorted, use two pointers, starting at the beginnings of Alice's and Bob's lists, and adjust them based on the comparison of their sums to find the correct swap.
This C solution first sorts both arrays and calculates the required delta. Two pointers are used to traverse both arrays, adjusting based on whether the sum of Bob's current candy size minus Alice's is less than, equal to, or greater than the delta. If an equal delta is found, it denotes a valid swap, and the function returns the pair.
Complexity
Time Complexity: O(n log n + m log m), due to the sorting step. The subsequent linear scan is O(n + m).
Space Complexity: O(1), with only a few additional variables used.
Approach 3: 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 diff, and use a hash table s to store the number of candies in Bob's candy boxes. Then, we traverse Alice's candy boxes, and for each candy count a, we check if a - diff is in the hash table s. If it exists, it means we have found a valid answer, and we return it.
The time complexity is O(m + n), and the space complexity is O(n). Where m and n are the number of candy boxes Alice and Bob have, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Calculating based on difference | Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes. This is because we iterate over each list once and use constant time checks for the existence of an element in Bob's collection. |
| Approach 2: Sorting and Two-Pointer Technique | Time Complexity: O(n log n + m log m), due to the sorting step. The subsequent linear scan is O(n + m). |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Difference Calculation with Hash Set | O(n + m) | O(n) | Best general solution when arrays are unsorted and fast lookup is needed |
| Sorting + Two Pointers | O(n log n + m log m) | O(1) or O(log n) | Useful if arrays are already sorted or when avoiding extra hash memory |
Video Solution
Leetcode 888. Fair Candy Swap [Java] • if else statement • 6,509 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Fair Candy Swap easy or hard?
Fair Candy Swap Python/Java solution
How to solve Fair Candy Swap in O(n)?
What is the best approach for Fair Candy Swap?
Is Fair Candy Swap asked at Google/Amazon/Meta?
What data structure is used in Fair Candy Swap?
What is the time complexity of Fair Candy Swap?
Ready to solve this problem?
Practice Fair Candy Swap with our built-in code editor and test cases.
Practice on FleetCode