Fair Candy Swap solution and explanation
Google
9 more videos on this problem
Leetcode 888. Fair Candy Swap [Java]if else statement · 7:05 · 6K views
Fair Candy Swap Leetcode C++ O(N)Code with Alisha · 8:59 · 4K views
888. Fair Candy Swap | LEETCODE EASYcode Explainer · 5:59 · 4K views
LeetCode 888 : Fair Candy Swap || EASY || JAVA || Detailed SolutionCodeGPT · 9:18 · 3K views
888. Fair Candy Swap (Leetcode Easy)Programming Live with Larry · 6:51 · 2K views
Leetcode Problem 888: Fair Candy Swap Solution ExplainedMohit Chhabra · 27:49 · 1K views
LeetCode 888 | Fair Candy Swap | Math | Equality | JavaSleepy Cracker · 5:42 · 808 views
How to Solve "888 Fair Candy Swap" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 11:52 · 558 views
Leetcode solving: 888 Fair Candy SwapMath Geeks · 3:09 · 426 views
Leetcode 888. Fair Candy SwapElite Code · 26:53 · 358 views
The problem
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.
def fairCandySwap(aliceSizes, bobSizes):
sumA = sum(aliceSizes)
sumB = sum(bobSizes)
delta = (sumB - sumA) // 2
setB = set(bobSizes)
for x in aliceSizes:
if x + delta in setB:
return [x, x + delta]import java.util.HashSet;
import java.util.Set;
public 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> setB = new HashSet<>();
for (int y : bobSizes) setB.add(y);
for (int x : aliceSizes) {
if (setB.contains(x + delta)) {
return new int[]{x, x + delta};
}
}
return null; // This line should not be reached
}
}#include <vector>
#include <unordered_set>
std::vector<int> fairCandySwap(std::vector<int>& aliceSizes, std::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;
std::unordered_set<int> setB(bobSizes.begin(), bobSizes.end());
for (int x : aliceSizes) {
if (setB.count(x + delta)) {
return {x, x + delta};
}
}
return {}; // This line should not be reached
}var fairCandySwap = function(aliceSizes, bobSizes) {
let sumA = aliceSizes.reduce((a, b) => a + b, 0);
let sumB = bobSizes.reduce((a, b) => a + b, 0);
let delta = (sumB - sumA) / 2;
let setB = new Set(bobSizes);
for (let x of aliceSizes) {
if (setB.has(x + delta)) {
return [x, x + delta];
}
}
};#include <stdio.h>
#include <stdlib.h>
int* fairCandySwap(int* aliceSizes, int alen, int* bobSizes, int blen, int* returnSize){
int sumA = 0, sumB = 0;
for (int i = 0; i < alen; ++i) sumA += aliceSizes[i];
for (int i = 0; i < blen; ++i) sumB += bobSizes[i];
int delta = (sumB - sumA) / 2;
int* setB = (int*)calloc(100001, sizeof(int));
for (int i = 0; i < blen; ++i) setB[bobSizes[i]] = 1;
int* answer = (int*)malloc(2 * sizeof(int));
*returnSize = 2;
for (int i = 0; i < alen; ++i) {
int x = aliceSizes[i];
int y = x + delta;
if (y >= 1 && y <= 100000 && setB[y]) {
answer[0] = x;
answer[1] = y;
break;
}
}
free(setB);
return answer;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] FairCandySwap(int[] aliceSizes, int[] bobSizes) {
int sumA = 0, sumB = 0;
foreach (int x in aliceSizes) sumA += x;
foreach (int y in bobSizes) sumB += y;
int delta = (sumB - sumA) / 2;
HashSet<int> setB = new HashSet<int>(bobSizes);
foreach (int x in aliceSizes) {
if (setB.Contains(x + delta)) {
return new int[]{x, x + delta};
}
}
return null; // This line should not be reached
}
}The Python solution makes use of built-in functions to compute sums and leverages set operations for efficient check of required conditions. The overall logic remains the same as described earlier.
Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes.
Space Complexity: O(m), due to use of an additional 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.
def fairCandySwap(aliceSizes, bobSizes):
aliceSizes.sort()
bobSizes.sort()
sumA = sum(aliceSizes)
sumB = sum(bobSizes)
delta = (sumB - sumA) // 2
i, j = 0, 0
while i < len(aliceSizes) and j < len(bobSizes):
diff = bobSizes[j] - aliceSizes[i]
if diff == delta:
return [aliceSizes[i], bobSizes[j]]
elif diff < delta:
j += 1
else:
i += 1import java.util.Arrays;
public class Solution {
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
Arrays.sort(aliceSizes);
Arrays.sort(bobSizes);
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
for (int y : bobSizes) sumB += y;
int delta = (sumB - sumA) / 2;
int i = 0, j = 0;
while (i < aliceSizes.length && j < bobSizes.length) {
int diff = bobSizes[j] - aliceSizes[i];
if (diff == delta) {
return new int[]{aliceSizes[i], bobSizes[j]};
} else if (diff < delta) {
j++;
} else {
i++;
}
}
return null; // This line should not be reached
}
}#include <vector>
#include <algorithm>
std::vector<int> fairCandySwap(std::vector<int>& aliceSizes, std::vector<int>& bobSizes) {
std::sort(aliceSizes.begin(), aliceSizes.end());
std::sort(bobSizes.begin(), bobSizes.end());
int sumA = 0, sumB = 0;
for (int x : aliceSizes) sumA += x;
for (int y : bobSizes) sumB += y;
int delta = (sumB - sumA) / 2;
int i = 0, j = 0;
while (i < aliceSizes.size() && j < bobSizes.size()) {
int diff = bobSizes[j] - aliceSizes[i];
if (diff == delta) {
return {aliceSizes[i], bobSizes[j]};
} else if (diff < delta) {
j++;
} else {
i++;
}
}
return {}; // This line should not be reached
}var fairCandySwap = function(aliceSizes, bobSizes) {
aliceSizes.sort((a, b) => a - b);
bobSizes.sort((a, b) => a - b);
let sumA = aliceSizes.reduce((a, b) => a + b, 0);
let sumB = bobSizes.reduce((a, b) => a + b, 0);
let delta = (sumB - sumA) / 2;
let i = 0, j = 0;
while (i < aliceSizes.length && j < bobSizes.length) {
let diff = bobSizes[j] - aliceSizes[i];
if (diff === delta) {
return [aliceSizes[i], bobSizes[j]];
} else if (diff < delta) {
j++;
} else {
i++;
}
}
};#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int* fairCandySwap(int* aliceSizes, int alen, int* bobSizes, int blen, int* returnSize) {
qsort(aliceSizes, alen, sizeof(int), compare);
qsort(bobSizes, blen, sizeof(int), compare);
int sumA = 0, sumB = 0;
for (int i = 0; i < alen; ++i) sumA += aliceSizes[i];
for (int i = 0; i < blen; ++i) sumB += bobSizes[i];
int delta = (sumB - sumA) / 2;
int i = 0, j = 0;
while (i < alen && j < blen) {
int diff = bobSizes[j] - aliceSizes[i];
if (diff == delta) {
int* answer = (int*)malloc(2 * sizeof(int));
answer[0] = aliceSizes[i];
answer[1] = bobSizes[j];
*returnSize = 2;
return answer;
} else if (diff < delta) {
++j;
} else {
++i;
}
}
return NULL; // This line should not be reached
}using System;
public class Solution {
public int[] FairCandySwap(int[] aliceSizes, int[] bobSizes) {
Array.Sort(aliceSizes);
Array.Sort(bobSizes);
int sumA = 0, sumB = 0;
foreach (int x in aliceSizes) sumA += x;
foreach (int y in bobSizes) sumB += y;
int delta = (sumB - sumA) / 2;
int i = 0, j = 0;
while (i < aliceSizes.Length && j < bobSizes.Length) {
int diff = bobSizes[j] - aliceSizes[i];
if (diff == delta) {
return new int[] { aliceSizes[i], bobSizes[j] };
} else if (diff < delta) {
j++;
} else {
i++;
}
}
return null; // This line should not be reached
}
}After sorting the candy sizes, this Python solution makes use of a single pass with two pointers to find the valid swap. The sort guarantees that once a valid swap is found, it is also optimal due to sorted order ensuring smaller and larger elements follow a linear order.
Time Complexity: O(n log n + m log m) for the sorting step.
Space Complexity: O(1), since it uses a constant number of extra variables.
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.
function fairCandySwap(aliceSizes: number[], bobSizes: number[]): number[] {
const s1 = aliceSizes.reduce((acc, cur) => acc + cur, 0);
const s2 = bobSizes.reduce((acc, cur) => acc + cur, 0);
const diff = (s1 - s2) >> 1;
const s = new Set(bobSizes);
for (const a of aliceSizes) {
const b = a - diff;
if (s.has(b)) {
return [a, b];
}
}
return [];
}func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
s1, s2 := 0, 0
s := map[int]bool{}
for _, a := range aliceSizes {
s1 += a
}
for _, b := range bobSizes {
s2 += b
s[b] = true
}
diff := (s1 - s2) / 2
for _, a := range aliceSizes {
if b := a - diff; s[b] {
return []int{a, b}
}
}
return nil
}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. |
| Approach 2: Sorting and Two-Pointer Technique | Time Complexity: O(n log n + m log m) for the sorting step. |
| Hash Table | – |
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 |
Frequently asked questions
Is Fair Candy Swap easy or hard?
Fair Candy Swap is classified as an easy problem on LeetCode with an acceptance rate above 60%. The challenge is recognizing the equation that balances both totals after the swap. Once the difference formula is derived, the implementation is straightforward using a hash set.
Fair Candy Swap Python/Java solution
Python and Java implementations typically compute the target difference and store Bob's candies in a set or HashSet. Each value in Alice's array is checked against the set for the matching partner. This approach keeps the solution concise and runs in O(n + m) time.
How to solve Fair Candy Swap in O(n)?
First compute the sums of both arrays and calculate target = (sumA - sumB) / 2. Store Bob's candy sizes in a hash set. Iterate through Alice's candies and check whether b = a - target exists in the set. The lookup is O(1), giving an overall O(n + m) time complexity.
What is the best approach for Fair Candy Swap?
The best approach uses a hash set and a difference equation. Compute the total candies for Alice and Bob, derive the required difference (sumA - sumB) / 2, and check for a matching value using constant-time hash lookups. This solution runs in O(n + m) time and is typically the expected interview answer.
Is Fair Candy Swap asked at Google/Amazon/Meta?
Fair Candy Swap is commonly used as an easy-level interview problem focusing on hash tables and mathematical reasoning. Variants of the problem have appeared in interviews at companies that emphasize array manipulation and set-based lookups, including large tech companies.
What data structure is used in Fair Candy Swap?
The most efficient solution uses a hash set to store one participant's candy sizes. This allows constant-time membership checks while iterating through the other array. Some implementations also use sorting and two-pointer traversal instead of hashing.
What is the time complexity of Fair Candy Swap?
The optimal hash-set solution runs in O(n + m) time where n and m are the lengths of Alice's and Bob's arrays. Space complexity is O(n) to store Bob's candies in a set. A sorting-based solution takes O(n log n + m log m) time due to sorting.