Fair Candy Swap

Easy
483.

Fair Candy Swap

Fair Candy Swap is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.

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 <= 10000
  • 1 <= aliceSizes[i], bobSizes[j] <= 100000
  • A fair swap always exists.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} aliceSizes
 * @param {number[]} bobSizes
 * @return {number[]}
 */
var fairCandySwap = function(aliceSizes, bobSizes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 10000
  • 1 <= aliceSizes[i], bobSizes[j] <= 100000
  • A fair swap always exists.

Hints for Fair Candy Swap

  1. Hint 1

    Write down what the totals become after swapping x for y: sumA - x + y and sumB - y + x.

  2. Hint 2

    Setting those equal gives y = x - (sumA - sumB) / 2. The whole problem collapses to that one equation.

  3. Hint 3

    Put Bob's sizes in a set, then try Alice's sizes in increasing order and return the first x whose 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

  1. Compute sumA and sumB, then delta = (sumA - sumB) / 2.
  2. Load every one of Bob's sizes into a hash set.
  3. Sort Alice's sizes ascending and scan them; for each x, check whether x - delta is in Bob's set.
  4. Return [x, x - delta] for the first hit — the smallest valid x.

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.
  • delta must 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