Fair Candy Swap — Solution in Python, Java & C++
Fair Candy Swap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and hash table.
Fair Candy Swap is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Alice and Bob have candy boxes: aliceSizes[i] is the number of candies in Alice's i-th box, and bobSizes[j] is the number in Bob's j-th box.
They want to swap exactly one box each so that afterwards they hold the same total number of candies. Return an array [x, y] where x is the size of the box Alice gives and y is the size of the box Bob gives.
At least one answer exists. If several do, return the one with the smallest x.
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 <= 100001 <= aliceSizes[i], bobSizes[j] <= 100000A fair swap always exists.
Hints for Fair Candy Swap
Hint 1
Write down what the totals become after swapping
xfory:sumA - x + yandsumB - y + x.Hint 2
Setting those equal gives
y = x - (sumA - sumB) / 2. The whole problem collapses to that one equation.Hint 3
Put Bob's sizes in a set, then try Alice's sizes in increasing order and return the first
xwhose partner exists.
How to solve Fair Candy Swap
After the swap Alice holds sumA - x + y and Bob holds sumB - y + x. Equating them fixes y in terms of x, so only a membership test remains.
Approach
- Compute
sumAandsumB, thendelta = (sumA - sumB) / 2. - Load every one of Bob's sizes into a hash set.
- Sort Alice's sizes ascending and scan them; for each
x, check whetherx - deltais in Bob's set. - Return
[x, x - delta]for the first hit — the smallest validx.
Why it works
sumA - x + y = sumB - y + x rearranges to 2(y - x) = sumB - sumA, i.e. y = x - (sumA - sumB)/2. The totals differ by an even amount whenever a solution exists, so delta is always an integer.
Complexity
- Time —
O(n log n + m) — the sort dominates - Space —
O(m) for Bob's set
Pitfalls
- Scanning Alice's array in its original order returns a valid answer but not the smallest
x. - Testing every
(i, j)pair is O(n·m) and times out at the stated limits. deltamust be computed as an exact integer — halving before subtracting invites rounding mistakes.
Reference solution
Python
from typing import List
def fairCandySwap(aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
delta = (sum(aliceSizes) - sum(bobSizes)) // 2
bset = set(bobSizes)
for x in sorted(aliceSizes):
if x - delta in bset:
return [x, x - delta]
return []Java
public static int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
long sa = 0, sb = 0;
for (int x : aliceSizes) sa += x;
for (int x : bobSizes) sb += x;
long delta = (sa - sb) / 2;
HashSet<Long> bset = new HashSet<>();
for (int x : bobSizes) bset.add((long) x);
int[] cands = aliceSizes.clone();
Arrays.sort(cands);
for (int x : cands) {
long y = x - delta;
if (bset.contains(y)) return new int[] { x, (int) y };
}
return new int[0];
}C++
vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
long long sa = 0, sb = 0;
for (int x : aliceSizes) sa += x;
for (int x : bobSizes) sb += x;
long long delta = (sa - sb) / 2;
unordered_set<long long> bset;
for (int x : bobSizes) bset.insert((long long) x);
vector<int> cands = aliceSizes;
sort(cands.begin(), cands.end());
for (int x : cands) {
long long y = (long long) x - delta;
if (bset.count(y)) return { x, (int) y };
}
return {};
}JavaScript
var fairCandySwap = function(aliceSizes, bobSizes) {
let sa = 0, sb = 0;
for (let i = 0; i < aliceSizes.length; i++) sa += aliceSizes[i];
for (let i = 0; i < bobSizes.length; i++) sb += bobSizes[i];
const delta = (sa - sb) / 2;
const bset = {};
for (let i = 0; i < bobSizes.length; i++) bset[String(bobSizes[i])] = true;
const cands = aliceSizes.slice().sort(function(a, b) { return a - b; });
for (let i = 0; i < cands.length; i++) {
const y = cands[i] - delta;
if (bset[String(y)] === true) return [cands[i], y];
}
return [];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets