# Fair Candy Swap
**Difficulty:** EASY
[External](https://leetcode.com/problems/fair-candy-swap)
Canonical: https://scaleengineer.com/dsa/problems/fair-candy-swap
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy), [Odoo](https://scaleengineer.com/companies/odoo)
---
## 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 a_n 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 <= 104`
* `1 <= 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.

# Approaches
## Brute Force with Nested Loops
This is the most straightforward and intuitive approach. We simply try every possible swap and check if it's a fair one. We calculate the initial total candies for Alice and Bob. Then, we use nested loops to iterate through every possible pair of candy boxes, one from Alice and one from Bob. For each pair, we check if swapping them would result in both having the same total amount of candy. The first such pair we find is our answer.
**Time:** O(N * M), where N is the length of `aliceSizes` and M is the length of `bobSizes`. Calculating the initial sums takes O(N + M), but this is dominated by the nested loops which perform N * M comparisons. · **Space:** O(1), as we only use a few variables to store the sums and loop indices, not dependent on the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1).
**Cons:** Highly inefficient for large input arrays, with a quadratic time complexity.; Likely to cause a 'Time Limit Exceeded' error on most coding platforms.
### Explanation
The algorithm begins by computing the total sum of candies for Alice (`sumA`) and Bob (`sumB`). The core of the problem is to find a candy box `x` from Alice and `y` from Bob such that after the swap, their new totals are equal. The new total for Alice would be `sumA - x + y`, and for Bob, `sumB - y + x`. We need to find `x` and `y` that satisfy `sumA - x + y = sumB - y + x`.

To find this pair, we can iterate through all of Alice's boxes. For each of her boxes `x`, we iterate through all of Bob's boxes `y` and check if the equality holds. As soon as we find a pair `(x, y)` that satisfies the condition, we can return it as the answer.

```java
class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sumA = 0;
        for (int x : aliceSizes) {
            sumA += x;
        }
        int sumB = 0;
        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 null; // Should not be reached as an answer is guaranteed
    }
}
```
### Algorithm
- Calculate `sumA`, the sum of all elements in `aliceSizes`.
- Calculate `sumB`, the sum of all elements in `bobSizes`.
- Iterate through each element `x` in `aliceSizes` using an outer loop.
- Inside this loop, iterate through each element `y` in `bobSizes` using an inner loop.
- For each pair `(x, y)`, check if swapping them makes the totals equal. The condition is `sumA - x + y == sumB - y + x`.
- Since an answer is guaranteed to exist, the first pair that satisfies this condition is a valid solution. Return `[x, y]`.

## Sorting and Two Pointers
A more optimized approach involves sorting both arrays first. After sorting, we can use a two-pointer technique to find the correct pair of candy boxes to swap. By moving the pointers intelligently based on the comparison, we can find the solution in a single pass through the sorted arrays, which is much faster than the nested loops of the brute-force method.
**Time:** O(N log N + M log M). The sorting of `aliceSizes` takes O(N log N) and `bobSizes` takes O(M log M). The subsequent two-pointer scan takes O(N + M). The sorting steps are the bottleneck. · **Space:** O(log N + log M) to O(N + M), depending on the sorting algorithm's implementation. This space is for the recursion stack or temporary arrays used by sorting. For instance, Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
**Pros:** Significantly more efficient than the brute-force approach.; Space-efficient, as it typically uses O(log N + log M) space for sorting, which is better than the O(M) or O(N) space of the hash set approach.
**Cons:** The time complexity is dominated by sorting, making it slower than the linear-time hash set approach.; Modifies the input arrays by sorting them, which might not be desirable in some contexts (though a copy can be made).
### Explanation
First, we establish the mathematical relationship for the swap. If Alice swaps `x` for `y`, her new total is `sumA - x + y`. Bob's is `sumB - y + x`. For these to be equal, `sumA - x + y = sumB - y + x`, which simplifies to `x - y = (sumA - sumB) / 2`. Let's call this target difference `diff`.

Our goal is to find an `x` in `aliceSizes` and a `y` in `bobSizes` that satisfy this equation. By sorting both arrays, we can search for this pair efficiently. We use two pointers, `i` starting at the beginning of the sorted `aliceSizes` and `j` at the beginning of the sorted `bobSizes`. We compare `aliceSizes[i] - bobSizes[j]` with our target `diff`. If the current difference is smaller than `diff`, we need to increase it by picking a larger `x`, so we advance pointer `i`. If it's larger, we need to decrease it by picking a larger `y`, so we advance pointer `j`. If they are equal, we've found our answer.

```java
import java.util.Arrays;

class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sumA = 0;
        for (int x : aliceSizes) sumA += x;
        int sumB = 0;
        for (int y : bobSizes) sumB += y;

        int diff = (sumA - sumB) / 2;
        
        Arrays.sort(aliceSizes);
        Arrays.sort(bobSizes);

        int i = 0, j = 0;
        while (i < aliceSizes.length && j < bobSizes.length) {
            int currentDiff = aliceSizes[i] - bobSizes[j];
            if (currentDiff == diff) {
                return new int[]{aliceSizes[i], bobSizes[j]};
            } else if (currentDiff < diff) {
                i++;
            } else {
                j++;
            }
        }
        return null; // Should not be reached
    }
}
```
### Algorithm
- Calculate `sumA` (sum of `aliceSizes`) and `sumB` (sum of `bobSizes`).
- Determine the required difference in the swapped items: `diff = (sumA - sumB) / 2`. The goal is to find `x` from Alice and `y` from Bob such that `x - y = diff`.
- Sort both `aliceSizes` and `bobSizes` arrays in ascending order.
- Initialize two pointers, `i = 0` for `aliceSizes` and `j = 0` for `bobSizes`.
- Loop while both pointers are within their array bounds:
  - If `aliceSizes[i] - bobSizes[j] == diff`, a match is found. Return `[aliceSizes[i], bobSizes[j]]`.
  - If `aliceSizes[i] - bobSizes[j] < diff`, the difference is too small. We need a larger `x` to increase it, so increment `i`.
  - If `aliceSizes[i] - bobSizes[j] > diff`, the difference is too large. We need a larger `y` to decrease it, so increment `j`.

## Optimized Search with a Hash Set
The most time-efficient solution uses a hash set to optimize the search. The core idea is to transform the problem from a search in a nested loop (O(N*M)) to a series of lookups in a hash set (O(N) lookups at O(1) each). We can determine the exact value Bob needs to give for any given value Alice gives. Then, we can check if Bob possesses a candy box of that exact value in constant average time using the hash set.
**Time:** O(N + M), where N and M are the lengths of the arrays. It takes O(N) to calculate `sumA`, O(M) to calculate `sumB` and populate the set, and O(N) to iterate through `aliceSizes` with O(1) lookups. The total is O(N + M). · **Space:** O(M), where M is the length of `bobSizes`. This space is used to store Bob's candy sizes in the hash set. To optimize, we could choose to put the smaller of the two arrays into the set.
**Pros:** Optimal time complexity of O(N + M).; Conceptually simple, leveraging a common data structure to optimize search.
**Cons:** Requires extra space to store one of the arrays in a hash set, which could be significant if the array is large.
### Explanation
We start with the same mathematical foundation: `sumA - x + y = sumB - y + x`. This can be rearranged to solve for `y` in terms of `x`: `2y = sumB - sumA + 2x`, which gives `y = x + (sumB - sumA) / 2`. Let `diff = (sumB - sumA) / 2`.

The algorithm is as follows:
1. First, calculate `sumA` and `sumB`.
2. To quickly check if Bob has the required candy `y`, we first store all of Bob's candy sizes in a `HashSet`. This takes O(M) time and space, where M is the number of Bob's candy boxes.
3. Then, we iterate through Alice's candy boxes. For each box `x`, we calculate the target value `y = x + diff`.
4. We then check if this calculated `y` exists in our hash set of Bob's candies. This check is, on average, an O(1) operation.
5. The first time we find such a `y`, we have found our answer and can return `[x, y]`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sumA = 0;
        for (int x : aliceSizes) {
            sumA += x;
        }
        int sumB = 0;
        Set<Integer> setB = new HashSet<>();
        for (int y : bobSizes) {
            sumB += y;
            setB.add(y);
        }

        int diff = (sumB - sumA) / 2;
        
        for (int x : aliceSizes) {
            int y = x + diff;
            if (setB.contains(y)) {
                return new int[]{x, y};
            }
        }
        
        return null; // Should not be reached
    }
}
```
### Algorithm
- Calculate `sumA` and `sumB`.
- Calculate the target difference `diff = (sumB - sumA) / 2`. The equation we need to satisfy is `y = x + diff`.
- Create a `HashSet` and populate it with all of Bob's candy sizes. This allows for O(1) average time lookups.
- Iterate through each candy box `x` in `aliceSizes`.
- For each `x`, calculate the required candy box size `y` that Bob must have: `y = x + diff`.
- Check if the hash set contains `y`.
- If it does, we have found the correct pair. Return `[x, y]`.

# Solutions
### Java

```java
class Solution {
public
  int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
    int s1 = 0, s2 = 0;
    Set<Integer> s = new HashSet<>();
    for (int a : aliceSizes) {
      s1 += a;
    }
    for (int b : bobSizes) {
      s.add(b);
      s2 += b;
    }
    int diff = (s1 - s2) >> 1;
    for (int a : aliceSizes) {
      int target = a - diff;
      if (s.contains(target)) {
        return new int[]{a, target};
      }
    }
    return null;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> fairCandySwap(vector<int> &aliceSizes, vector<int> &bobSizes) {
    int s1 = accumulate(aliceSizes.begin(), aliceSizes.end(), 0);
    int s2 = accumulate(bobSizes.begin(), bobSizes.end(), 0);
    int diff = (s1 - s2) >> 1;
    unordered_set<int> s(bobSizes.begin(), bobSizes.end());
    vector<int> ans;
    for (int &a : aliceSizes) {
      int target = a - diff;
      if (s.count(target)) {
        ans = vector<int>{a, target};
        break;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]: diff = (sum(aliceSizes) - sum(bobSizes)) >> 1 s = set(bobSizes) for a in aliceSizes: target = a - diff if target in s: return [a, target]

```