# LeetCode 888: Fair Candy Swap

## Problem Restatement

Alice and Bob each have several candy boxes.

`aliceSizes[i]` is the number of candies in Alice's `i`th box.

`bobSizes[j]` is the number of candies in Bob's `j`th box.

They want to exchange exactly one box each so that after the swap, they have the same total number of candies.

Return:

```python
[alice_box, bob_box]
```

where `alice_box` is the size of the box Alice gives to Bob, and `bob_box` is the size of the box Bob gives to Alice.

If there are multiple valid answers, we may return any one of them. The problem guarantees that at least one valid answer exists. LeetCode states these arrays as `aliceSizes` and `bobSizes`, and asks for one valid swap.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `aliceSizes`, Alice's candy box sizes |
| Input | `bobSizes`, Bob's candy box sizes |
| Output | `[x, y]`, where Alice gives `x` and Bob gives `y` |
| Goal | Make both total candy counts equal |
| Valid answer | Guaranteed to exist |
| Multiple answers | Any valid answer is accepted |

Function shape:

```python
def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

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

Alice starts with:

```text
1 + 1 = 2
```

Bob starts with:

```text
2 + 2 = 4
```

If Alice gives `1` and Bob gives `2`, then Alice has:

```text
2 - 1 + 2 = 3
```

Bob has:

```text
4 - 2 + 1 = 3
```

Both have `3`, so `[1, 2]` is valid.

Example 2:

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

Alice starts with `3`.

Bob starts with `5`.

Swap Alice's `1` with Bob's `2`:

```text
Alice: 3 - 1 + 2 = 4
Bob:   5 - 2 + 1 = 4
```

So the answer is `[1, 2]`.

Example 3:

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

Alice starts with `2`.

Bob starts with `4`.

Swap `2` and `3`:

```text
Alice: 2 - 2 + 3 = 3
Bob:   4 - 3 + 2 = 3
```

So the answer is `[2, 3]`.

## First Thought: Try Every Pair

A direct approach is to try every box from Alice and every box from Bob.

For each pair `(x, y)`, check whether swapping them makes the totals equal.

```python
class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sum_alice = sum(aliceSizes)
        sum_bob = sum(bobSizes)

        for x in aliceSizes:
            for y in bobSizes:
                if sum_alice - x + y == sum_bob - y + x:
                    return [x, y]

        return []
```

This is correct, but it may be slow.

If both arrays have many boxes, this checks too many pairs.

## Problem With Brute Force

Let:

```text
A = len(aliceSizes)
B = len(bobSizes)
```

The brute force approach checks:

```text
A * B
```

pairs.

The constraints allow both arrays to be large, so we need a faster way.

## Key Insight

Let:

```text
sumA = sum(aliceSizes)
sumB = sum(bobSizes)
```

Suppose Alice gives a box of size `x`, and Bob gives a box of size `y`.

After the swap:

```text
Alice has sumA - x + y
Bob has   sumB - y + x
```

We need:

```text
sumA - x + y = sumB - y + x
```

Rearrange:

```text
2y = sumB - sumA + 2x
```

So:

```text
y = x + (sumB - sumA) / 2
```

That means for each Alice box `x`, we know exactly what Bob box `y` is needed.

So we can store Bob's box sizes in a set and check quickly.

## Algorithm

Compute:

```python
sum_alice = sum(aliceSizes)
sum_bob = sum(bobSizes)
```

The amount Bob's box must exceed Alice's box by is:

```python
delta = (sum_bob - sum_alice) // 2
```

For each `x` in `aliceSizes`, we need:

```python
y = x + delta
```

If `y` exists in Bob's set, return:

```python
[x, y]
```

## Walkthrough

Use:

```text
aliceSizes = [1, 2]
bobSizes = [2, 3]
```

Compute sums:

| Person | Sum |
|---|---:|
| Alice | 3 |
| Bob | 5 |

Bob has `2` more candies than Alice.

After one swap, the difference must be removed from both sides. So Bob needs to give Alice a box that is larger by:

```text
(5 - 3) / 2 = 1
```

So for Alice's box `x`, Bob's needed box is:

```text
x + 1
```

Try Alice's box `1`:

```text
needed Bob box = 1 + 1 = 2
```

Bob has a box of size `2`.

Return:

```python
[1, 2]
```

## Correctness

Let `sumA` be Alice's original total and `sumB` be Bob's original total.

Suppose the algorithm returns `[x, y]`.

The algorithm only returns such a pair when `x` is in `aliceSizes`, `y` is in `bobSizes`, and:

```text
y = x + (sumB - sumA) / 2
```

Then:

```text
2(y - x) = sumB - sumA
```

Rearranging gives:

```text
sumA - x + y = sumB - y + x
```

So after the swap, Alice and Bob have equal totals. Therefore, the returned pair is valid.

Now suppose a valid answer exists, as guaranteed by the problem. Let that answer be `[x, y]`.

Because the swap is valid:

```text
sumA - x + y = sumB - y + x
```

Rearranging gives:

```text
y = x + (sumB - sumA) / 2
```

When the algorithm checks this Alice box `x`, it computes exactly this required `y`. Since `y` is one of Bob's boxes, it will be found in the set, and the algorithm will return a valid answer.

Thus, the algorithm always returns a correct swap.

## Complexity

Let:

```text
A = len(aliceSizes)
B = len(bobSizes)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(A + B)` | We compute sums, build a set, and scan Alice's boxes |
| Space | `O(B)` | We store Bob's box sizes in a set |

## Implementation

```python
class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sum_alice = sum(aliceSizes)
        sum_bob = sum(bobSizes)

        delta = (sum_bob - sum_alice) // 2
        bob_set = set(bobSizes)

        for x in aliceSizes:
            y = x + delta

            if y in bob_set:
                return [x, y]

        return []
```

## Code Explanation

We first compute both totals:

```python
sum_alice = sum(aliceSizes)
sum_bob = sum(bobSizes)
```

Then compute how much larger Bob's chosen box must be than Alice's chosen box:

```python
delta = (sum_bob - sum_alice) // 2
```

We store Bob's box sizes in a set:

```python
bob_set = set(bobSizes)
```

This lets us check whether a needed box size exists in expected `O(1)` time.

For each Alice box:

```python
for x in aliceSizes:
```

the needed Bob box is:

```python
y = x + delta
```

If Bob has that box, we return the swap:

```python
if y in bob_set:
    return [x, y]
```

The final return is only a fallback. The problem guarantees that a valid answer exists.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.fairCandySwap([1, 1], [2, 2]) == [1, 2]
    assert s.fairCandySwap([1, 2], [2, 3]) == [1, 2]
    assert s.fairCandySwap([2], [1, 3]) == [2, 3]
    assert s.fairCandySwap([1, 2, 5], [2, 4]) == [5, 4]

    result = s.fairCandySwap([8, 4], [1, 2, 3, 7])
    x, y = result
    assert sum([8, 4]) - x + y == sum([1, 2, 3, 7]) - y + x

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,1]`, `[2,2]` | Standard small example |
| `[1,2]`, `[2,3]` | Different totals with simple swap |
| `[2]`, `[1,3]` | Alice has one box |
| `[1,2,5]`, `[2,4]` | Larger Alice box goes to Bob |
| Custom validation | Checks equality after returned swap |