# LeetCode 870: Advantage Shuffle

## Problem Restatement

We are given two integer arrays:

```python
nums1
nums2
```

Both arrays have the same length.

The advantage of `nums1` over `nums2` is the number of indices `i` where:

```python
nums1[i] > nums2[i]
```

We may rearrange `nums1` in any order.

Return any permutation of `nums1` that maximizes its advantage over `nums2`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums1`, the array we may reorder |
| Input | `nums2`, the fixed comparison array |
| Output | A permutation of `nums1` |
| Goal | Maximize the count of positions where `answer[i] > nums2[i]` |

Function shape:

```python
class Solution:
    def advantageCount(self, nums1: list[int], nums2: list[int]) -> list[int]:
        ...
```

## Examples

Example 1:

```python
nums1 = [2, 7, 11, 15]
nums2 = [1, 10, 4, 11]
```

One optimal answer is:

```python
[2, 11, 7, 15]
```

Compare by index:

| Index | Answer | `nums2` | Win? |
|---|---:|---:|---|
| `0` | `2` | `1` | yes |
| `1` | `11` | `10` | yes |
| `2` | `7` | `4` | yes |
| `3` | `15` | `11` | yes |

The advantage is `4`.

Example 2:

```python
nums1 = [12, 24, 8, 32]
nums2 = [13, 25, 32, 11]
```

One optimal answer is:

```python
[24, 32, 8, 12]
```

Compare by index:

| Index | Answer | `nums2` | Win? |
|---|---:|---:|---|
| `0` | `24` | `13` | yes |
| `1` | `32` | `25` | yes |
| `2` | `8` | `32` | no |
| `3` | `12` | `11` | yes |

The advantage is `3`.

## First Thought: Try All Permutations

A direct approach is to try every permutation of `nums1`.

For each permutation:

1. Compare it with `nums2`.
2. Count how many indices win.
3. Keep the permutation with the best score.

This is correct but impossible for large inputs.

There are:

```python
n!
```

possible permutations.

We need a greedy method.

## Key Insight

This problem is similar to assigning cards.

For each value in `nums2`, we want to beat it using the smallest possible value from `nums1`.

Why the smallest winning value?

If we can beat `13` with `24`, using `32` is wasteful because `32` may be needed to beat a larger value later.

So the greedy rule is:

1. Use the smallest available number that can beat the current opponent.
2. If no available number can beat it, sacrifice the smallest available number.

A convenient way to implement this is to sort both sides.

Sort `nums1`.

Sort the indices of `nums2` by their values.

Then process `nums2` from largest to smallest.

For the largest remaining value in `nums2`:

- If the largest remaining number in `nums1` can beat it, use that number.
- Otherwise, the largest remaining number in `nums2` cannot be beaten by anything left, so sacrifice the smallest remaining number in `nums1`.

This gives a clean two-pointer solution.

## Algorithm

Sort `nums1`.

Create an array of indices from `nums2`, sorted by `nums2[index]`.

Use two pointers on sorted `nums1`:

```python
left = 0
right = n - 1
```

Use another pointer over sorted `nums2` indices from largest to smallest.

For each index `idx` in descending order of `nums2[idx]`:

1. If `nums1[right] > nums2[idx]`, assign it to `answer[idx]`.
2. Move `right` left.
3. Otherwise, assign `nums1[left]` to `answer[idx]`.
4. Move `left` right.

At the end, return `answer`.

## Correctness

Consider the largest remaining value in `nums2`.

If the largest remaining value in `nums1` can beat it, assigning that largest value produces one win. This is safe because no smaller available `nums1` value can be more useful against this largest `nums2` value than a winning assignment now.

If the largest remaining value in `nums1` cannot beat it, then no remaining value in `nums1` can beat it. So this position is unwinnable. The best choice is to sacrifice the smallest remaining value from `nums1`, preserving larger values for smaller future `nums2` values that they may still beat.

This greedy choice preserves the maximum possible number of wins at every step.

Since the algorithm processes all `nums2` values from largest to smallest and makes the optimal choice for each current largest remaining opponent, the final arrangement maximizes the advantage.

## Complexity

Let:

```python
n = len(nums1)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting `nums1` and sorting indices of `nums2` |
| Space | `O(n)` | The answer array and sorted index array |

## Implementation

```python
class Solution:
    def advantageCount(self, nums1: list[int], nums2: list[int]) -> list[int]:
        n = len(nums1)

        nums1.sort()
        indices = sorted(range(n), key=lambda i: nums2[i])

        answer = [0] * n

        left = 0
        right = n - 1

        for idx in reversed(indices):
            if nums1[right] > nums2[idx]:
                answer[idx] = nums1[right]
                right -= 1
            else:
                answer[idx] = nums1[left]
                left += 1

        return answer
```

## Code Explanation

We first sort `nums1`:

```python
nums1.sort()
```

This lets us take either the smallest remaining value or the largest remaining value.

Then we sort indices of `nums2`:

```python
indices = sorted(range(n), key=lambda i: nums2[i])
```

We sort indices instead of values because the answer must be placed back in the original positions of `nums2`.

The result array starts empty:

```python
answer = [0] * n
```

The two pointers represent the unused part of `nums1`:

```python
left = 0
right = n - 1
```

We process the largest `nums2` values first:

```python
for idx in reversed(indices):
```

If the largest remaining `nums1` value can win:

```python
if nums1[right] > nums2[idx]:
```

we use it:

```python
answer[idx] = nums1[right]
right -= 1
```

Otherwise, this `nums2[idx]` cannot be beaten by anything left, so we sacrifice the smallest remaining value:

```python
answer[idx] = nums1[left]
left += 1
```

Finally:

```python
return answer
```

returns a permutation of `nums1` with maximum advantage.

## Testing

```python
def advantage_score(a, b):
    return sum(x > y for x, y in zip(a, b))

def test_advantage_count():
    s = Solution()

    nums1 = [2, 7, 11, 15]
    nums2 = [1, 10, 4, 11]
    ans = s.advantageCount(nums1[:], nums2)
    assert sorted(ans) == sorted(nums1)
    assert advantage_score(ans, nums2) == 4

    nums1 = [12, 24, 8, 32]
    nums2 = [13, 25, 32, 11]
    ans = s.advantageCount(nums1[:], nums2)
    assert sorted(ans) == sorted(nums1)
    assert advantage_score(ans, nums2) == 3

    nums1 = [1, 1, 1, 1]
    nums2 = [2, 2, 2, 2]
    ans = s.advantageCount(nums1[:], nums2)
    assert sorted(ans) == sorted(nums1)
    assert advantage_score(ans, nums2) == 0

    nums1 = [5, 5, 6, 6]
    nums2 = [4, 5, 5, 7]
    ans = s.advantageCount(nums1[:], nums2)
    assert sorted(ans) == sorted(nums1)
    assert advantage_score(ans, nums2) == 3

    print("all tests passed")

test_advantage_count()
```

Test meaning:

| Test | Why |
|---|---|
| `[2, 7, 11, 15]` vs `[1, 10, 4, 11]` | All positions can be won |
| `[12, 24, 8, 32]` vs `[13, 25, 32, 11]` | Requires sacrificing against `32` |
| All `nums1` values too small | Checks zero advantage |
| Duplicate values | Checks equality and repeated numbers |