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 in 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 a n integer arrayanswer whereanswer[0]is the number of candies in the box that Alice must exchange, andanswer[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.

Examples

Example 1

1
2

Input: aliceSizes = [1,1], bobSizes = [2,2]
Output: [1,2]

Example 2

1
2

Input: aliceSizes = [1,2], bobSizes = [2,3]
Output: [1,2]

Example 3

1
2

Input: aliceSizes = [2], bobSizes = [1,3]
Output: [2,3]

Constraints

  • 1 <= aliceSizes.length, bobSizes.length <= 10^4
  • 1 <= aliceSizes[i], bobSizes[j] <= 10^5
  • Alice and Bob have a different total number of candies.
  • There will be at least one valid answer for the given input.

Solution

Method 1 – Hash Set and Math

Intuition

If Alice gives away a box with a candies and Bob gives away a box with b candies, after the swap, their totals will be equal if:

sumA - a + b = sumB - b + a

This simplifies to:

a - b = (sumA - sumB) / 2

So, for each a in Alice’s boxes, if Bob has a box with b = a - delta, that’s the answer.

Approach

  1. Compute the total candies for Alice (sumA) and Bob (sumB).
  2. Compute delta = (sumA - sumB) / 2.
  3. Store all of Bob’s box sizes in a set for O(1) lookup.
  4. For each box size a in Alice’s list, check if a - delta exists in Bob’s set.
  5. Return [a, b] as soon as a valid pair is found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sumA = accumulate(A.begin(), A.end(), 0);
        int sumB = accumulate(B.begin(), B.end(), 0);
        int delta = (sumA - sumB) / 2;
        unordered_set<int> setB(B.begin(), B.end());
        for (int a : A) {
            int b = a - delta;
            if (setB.count(b)) return {a, b};
        }
        return {};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func fairCandySwap(A []int, B []int) []int {
    sumA, sumB := 0, 0
    for _, a := range A { sumA += a }
    for _, b := range B { sumB += b }
    delta := (sumA - sumB) / 2
    setB := make(map[int]struct{})
    for _, b := range B { setB[b] = struct{}{} }
    for _, a := range A {
        b := a - delta
        if _, ok := setB[b]; ok {
            return []int{a, b}
        }
    }
    return nil
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = 0, sumB = 0;
        for (int a : A) sumA += a;
        for (int b : B) sumB += b;
        int delta = (sumA - sumB) / 2;
        Set<Integer> setB = new HashSet<>();
        for (int b : B) setB.add(b);
        for (int a : A) {
            int b = a - delta;
            if (setB.contains(b)) return new int[]{a, b};
        }
        return new int[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun fairCandySwap(A: IntArray, B: IntArray): IntArray {
        val sumA = A.sum()
        val sumB = B.sum()
        val delta = (sumA - sumB) / 2
        val setB = B.toSet()
        for (a in A) {
            val b = a - delta
            if (b in setB) return intArrayOf(a, b)
        }
        return intArrayOf()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sumA = sum(aliceSizes)
        sumB = sum(bobSizes)
        delta = (sumA - sumB) // 2
        setB = set(bobSizes)
        for a in aliceSizes:
            b = a - delta
            if b in setB:
                return [a, b]
        return []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn fair_candy_swap(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
        let sum_a: i32 = a.iter().sum();
        let sum_b: i32 = b.iter().sum();
        let delta = (sum_a - sum_b) / 2;
        let set_b: std::collections::HashSet<_> = b.iter().cloned().collect();
        for &x in &a {
            let y = x - delta;
            if set_b.contains(&y) {
                return vec![x, y];
            }
        }
        vec![]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fairCandySwap(A: number[], B: number[]): number[] {
        const sumA = A.reduce((a, b) => a + b, 0);
        const sumB = B.reduce((a, b) => a + b, 0);
        const delta = (sumA - sumB) / 2;
        const setB = new Set(B);
        for (const a of A) {
            const b = a - delta;
            if (setB.has(b)) return [a, b];
        }
        return [];
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n and m are the lengths of aliceSizes and bobSizes. We compute sums and build a set in linear time, and then do a single pass.
  • 🧺 Space complexity: O(m), for storing Bob’s box sizes in a set.