Watch 10 video solutions for Fair Candy Swap, a easy level problem involving Array, Hash Table, Binary Search. This walkthrough by if else statement has 6,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem 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 | 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 |