Fair Candy Swap
Fair Candy Swap is a easy arrays & hashing problem solved with the hash set lookup pattern.
The best approach, optimal (hash set of bob's sizes), runs in O(n + m) time and O(m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
Alice and Bob each own some boxes of candy. aliceSizes[i] is the number of candies in Alice’s i-th box and bobSizes[j] the number in Bob’s j-th box. Their totals are different.
They want to end up with the same total by trading exactly one box each: Alice hands one of her boxes to Bob and receives one of Bob’s boxes in return.
Return [x, y], where x is the size of the box Alice gives and y the size of the box Bob gives. A valid trade is guaranteed to exist; if there are several, return any of them.
Examples
Example 1
- Input
aliceSizes = [1, 5], bobSizes = [3, 7]- Output
[1, 3]- Why
- Alice gives 1 and gets 3 (6 - 1 + 3 = 8); Bob gives 3 and gets 1 (10 - 3 + 1 = 8). Returning [5, 7] is also accepted.
Example 2
- Input
aliceSizes = [5, 3], bobSizes = [2]- Output
[5, 2]- Why
- Alice goes from 8 to 8 - 5 + 2 = 5 and Bob from 2 to 2 - 2 + 5 = 5.
Example 3
- Input
aliceSizes = [2, 2], bobSizes = [4, 4]- Output
[2, 4]- Why
- Both end with 6 candies. Duplicate box sizes do not matter.
Constraints
1 <= aliceSizes.length, bobSizes.length <= 10^41 <= aliceSizes[i], bobSizes[j] <= 10^5- The two totals are different, and at least one valid swap exists.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · m) | O(1) |
| Optimal (hash set of Bob's sizes) | O(n + m) | O(m) |
1Brute force
O(n · m)Every Alice box is paired with every Bob box.O(1)Only the two sums and loop variables.Try every pair of one Alice box and one Bob box and simulate the swap. Return the first pair after which both totals are equal.
- Compute sumA and sumB.
- For every x in aliceSizes and every y in bobSizes, check sumA - x + y == sumB - y + x.
- Return [x, y] for the first pair that works.
class Solution {
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
for (int y : bobSizes) sumB += y;
for (int x : aliceSizes) {
for (int y : bobSizes) {
if (sumA - x + y == sumB - y + x) {
return new int[] { x, y };
}
}
}
return new int[0];
}
}class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
sum_a, sum_b = sum(aliceSizes), sum(bobSizes)
for x in aliceSizes:
for y in bobSizes:
if sum_a - x + y == sum_b - y + x:
return [x, y]
return []class Solution {
public:
vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
for (int y : bobSizes) sumB += y;
for (int x : aliceSizes) {
for (int y : bobSizes) {
if (sumA - x + y == sumB - y + x) {
return {x, y};
}
}
}
return {};
}
};function fairCandySwap(aliceSizes, bobSizes) {
let sumA = 0, sumB = 0;
for (const x of aliceSizes) sumA += x;
for (const y of bobSizes) sumB += y;
for (const x of aliceSizes) {
for (const y of bobSizes) {
if (sumA - x + y === sumB - y + x) {
return [x, y];
}
}
}
return [];
}2Optimal (hash set of Bob's sizes)
O(n + m)One pass to build the set, one pass over Alice's boxes with O(1) lookups.O(m)The set holds Bob's distinct sizes.After the swap both totals must equal (sumA + sumB) / 2, so Alice must receive exactly delta = (sumB - sumA) / 2 more than she gives: y = x + delta. Put Bob's sizes in a hash set and, for each Alice box x, look up x + delta.
- Compute sumA, sumB and delta = (sumB - sumA) / 2.
- Insert every bobSizes value into a hash set.
- For each x in aliceSizes, if x + delta is in the set, return [x, x + delta].
class Solution {
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
for (int y : bobSizes) sumB += y;
int delta = (sumB - sumA) / 2;
Set<Integer> bob = new HashSet<>();
for (int y : bobSizes) bob.add(y);
for (int x : aliceSizes) {
if (bob.contains(x + delta)) {
return new int[] { x, x + delta };
}
}
return new int[0];
}
}class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
delta = (sum(bobSizes) - sum(aliceSizes)) // 2
bob = set(bobSizes)
for x in aliceSizes:
if x + delta in bob:
return [x, x + delta]
return []class Solution {
public:
vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
for (int y : bobSizes) sumB += y;
int delta = (sumB - sumA) / 2;
unordered_set<int> bob(bobSizes.begin(), bobSizes.end());
for (int x : aliceSizes) {
if (bob.count(x + delta)) {
return {x, x + delta};
}
}
return {};
}
};function fairCandySwap(aliceSizes, bobSizes) {
let sumA = 0, sumB = 0;
for (const x of aliceSizes) sumA += x;
for (const y of bobSizes) sumB += y;
const delta = (sumB - sumA) / 2;
const bob = new Set(bobSizes);
for (const x of aliceSizes) {
if (bob.has(x + delta)) {
return [x, x + delta];
}
}
return [];
}Edge cases to test
- Several valid swaps: any one of them is accepted
- One person owns a single box
- Alice has more candy than Bob, so she must hand over the bigger box
- Many repeated box sizes
Hints
Hint 1
If Alice gives x and receives y, her total changes by y - x and Bob's by x - y. What must y - x be?
Hint 2
The difference y - x is a fixed number: half of (Bob's total - Alice's total).
Hint 3
For each x in Alice's boxes, check whether x + delta is one of Bob's sizes, using a hash set.
FAQ
What is the best time complexity for Fair Candy Swap?
Optimal (hash set of Bob's sizes) runs in O(n + m) time and O(m) extra space. One pass to build the set, one pass over Alice's boxes with O(1) lookups.
Which pattern does Fair Candy Swap use?
It is a arrays & hashing problem that uses the hash set lookup pattern. Other problems with the same pattern: Longest Consecutive Sequence, Contains Duplicate, Maximize Area of Square Hole in Grid.
Is there a brute force solution for Fair Candy Swap?
Yes. Brute force takes O(n · m) time and O(1) space. Try every pair of one Alice box and one Bob box and simulate the swap.
Which edge cases should I test for Fair Candy Swap?
Several valid swaps: any one of them is accepted; One person owns a single box; Alice has more candy than Bob, so she must hand over the bigger box; Many repeated box sizes.