Code Implementation

class Solution:
    def fairCandySwap(self, A, B):
        sumA, sumB = sum(A), sum(B)
        diff = (sumA - sumB) // 2
        setB = set(B)
        for a in A:
            if (a - diff) in setB:
                return [a, a - diff]
      

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 diff = (sumA - sumB) / 2;
        unordered_set<int> setB(B.begin(), B.end());
        for (int a : A) {
            if (setB.count(a - diff)) {
                return {a, a - diff};
            }
        }
        return {};
    }
};
      

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 diff = (sumA - sumB) / 2;
        Set<Integer> setB = new HashSet<>();
        for (int b : B) setB.add(b);
        for (int a : A) {
            if (setB.contains(a - diff)) {
                return new int[]{a, a - diff};
            }
        }
        return new int[0];
    }
}
      

var fairCandySwap = function(A, B) {
    const sumA = A.reduce((a, b) => a + b, 0);
    const sumB = B.reduce((a, b) => a + b, 0);
    const diff = (sumA - sumB) / 2;
    const setB = new Set(B);
    for (let a of A) {
        if (setB.has(a - diff)) {
            return [a, a - diff];
        }
    }
};
      

Problem Description

You are given two integer arrays, A and B, representing the sizes of candies that Alice and Bob have, respectively. They want to exchange exactly one candy each so that after the swap, both have the same total amount of candy.

Find a pair of values (x from A, y from B) such that swapping them will equalize their total candy. Each input will have exactly one valid solution, and each candy can only be used once in the swap.

• Return the answer as an array: [x, y]
• Both A and B have at least one element
• Each element is a positive integer
• There is guaranteed to be one answer that works

Thought Process

At first glance, you might consider trying all possible pairs between A and B to see which swap equalizes the totals. However, this brute-force approach is inefficient, especially for larger arrays, since it checks every combination.

By thinking about the problem mathematically, we realize that we can find a relationship between the candy sizes to swap. If Alice gives up x and Bob gives up y, after swapping, Alice’s total is sumA - x + y and Bob’s is sumB - y + x. We want these totals to be equal.

This leads to a formula that allows us to directly compute the value to look for in Bob’s set, shifting our approach from brute-force to an optimized search.

Solution Approach

• Step 1: Calculate the sum of candies for Alice (sumA) and Bob (sumB).
• Step 2: Set up the equation: sumA - x + y = sumB - y + x. Rearranging, we find x - y = (sumA - sumB) / 2.
• Step 3: For every candy a in A, if there is a candy b in B such that a - b equals the difference from step 2, swapping a and b will balance the totals.
• Step 4: To check if b exists efficiently, store all candies in B in a set for O(1) lookups.
• Step 5: Iterate through A, for each a, check if a - diff exists in B. If it does, return [a, a - diff].

This approach leverages set lookups for efficiency and uses the mathematical relationship to avoid unnecessary checks, making it much faster than brute-force.

Example Walkthrough

Let’s use the example: A = [1, 2, 5], B = [2, 4]

1. sumA = 8 (1 + 2 + 5), sumB = 6 (2 + 4)
2. diff = (8 - 6) / 2 = 1
3. We want to find a in A and b in B such that a - b = 1
4. Iterate through A:
   • a = 1: 1 - 1 = 0, not in B
   • a = 2: 2 - 1 = 1, not in B
   • a = 5: 5 - 1 = 4, 4 is in B
5. So, swapping 5 (from A) and 4 (from B) equalizes the totals: [5, 4].

Time and Space Complexity

Brute-force approach: For each element in A, check every element in B → O(N * M) time, where N and M are the lengths of A and B.

Optimized approach:

• Calculating the sums: O(N + M)
• Building the set from B: O(M)
• Iterating through A and checking in the set: O(N)

Total time complexity: O(N + M)

Space complexity: O(M) for storing the set of B.

Summary

The Fair Candy Swap problem is elegantly solved by expressing the swap condition as a simple mathematical equation, allowing us to avoid brute-force checking. By leveraging hash sets for fast lookups and understanding the relationship between the two arrays, we achieve an efficient O(N + M) solution. This approach is both neat and practical, making use of core programming concepts like hashing and algebraic manipulation.