LeetCode 870: Advantage Shuffle

Problem Restatement

We are given two integer arrays:

nums1
nums2

Both arrays have the same length.

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

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

Function shape:

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

Examples

Example 1:

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

One optimal answer is:

[2, 11, 7, 15]

Compare by index:

The advantage is 4.

Example 2:

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

One optimal answer is:

[24, 32, 8, 12]

Compare by index:

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:

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:

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:

n = len(nums1)

Implementation

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:

nums1.sort()

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

Then we sort indices of nums2:

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:

answer = [0] * n

The two pointers represent the unused part of nums1:

left = 0
right = n - 1

We process the largest nums2 values first:

for idx in reversed(indices):

If the largest remaining nums1 value can win:

if nums1[right] > nums2[idx]:

we use it:

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

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

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

Finally:

return answer

returns a permutation of nums1 with maximum advantage.

Testing

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: