Advantage Shuffle: Greedy Matching with Sorted Arrays

You are given two integer arrays nums1 and nums2, both of the same length. You want to rearrange nums1 so that the number of indices where nums1[i] > nums2[i] is maximized. Return the rearranged nums1. This is LeetCode 870: Advantage Shuffle, a medium problem that teaches a powerful greedy matching strategy.

Why this problem matters

This problem is a modern version of the classic Tian Ji horse racing problem from ancient China. The story goes like this: a general named Tian Ji raced horses against the king. He could not win with equal matchups, so his advisor suggested a strategy. Use your weakest horse against the king's strongest (sacrifice it), then beat each remaining horse with the smallest horse that can still win. That is exactly the greedy strategy this problem requires.

The pattern of sorting one collection and then greedily matching elements against a target shows up in many problems. Once you internalize the logic of "use the cheapest resource that gets the job done, and throw away resources that cannot help," you can apply it to scheduling, assignment, and optimization problems across the board.

The brute force approach

The brute force solution tries every permutation of nums1 and checks how many indices satisfy nums1[i] > nums2[i]. With n elements, there are n! permutations, so this runs in O(n! * n) time. Even for n = 12, that is nearly 6 billion operations. We need something much faster.

from itertools import permutations

def advantageCount_brute(nums1, nums2):
    best = []
    best_count = -1
    for perm in permutations(nums1):
        count = sum(1 for i in range(len(nums2)) if perm[i] > nums2[i])
        if count > best_count:
            best_count = count
            best = list(perm)
    return best

The key insight: greedy matching

Sort nums1 in ascending order. Then process nums2 elements from largest to smallest. For each nums2 element, check whether the largest remaining element in nums1 can beat it. If it can, assign it (that is the cheapest winning move from the top). If it cannot, no element in nums1 can beat this opponent, so assign the smallest remaining element as a sacrifice.

This greedy choice works because of an exchange argument. If you use a large element from nums1 to beat a small element in nums2, you might not have anything left to beat a larger nums2 element. Processing nums2 from largest to smallest ensures you never waste a winning card on a matchup where a cheaper card would have worked.

Think of sorted nums1 as a deque. You pull from the right (largest) when you can win, and from the left (smallest) when you cannot. Each element is used exactly once, and the result array fills from the positions of the largest nums2 values down to the smallest.

Walking through it step by step

Let's trace through nums1 = [2, 7, 11, 15] and nums2 = [1, 10, 4, 11]. The greedy approach sorts nums1, processes nums2 from largest to smallest, and fills in the result.

After processing all four nums2 elements from largest to smallest, we get result = [2, 11, 7, 15]. Every element in the result beats its corresponding opponent, achieving 4 out of 4 wins.

The greedy solution

from collections import deque

def advantageCount(nums1, nums2):
    sorted_a = deque(sorted(nums1))
    order = sorted(range(len(nums2)), key=lambda i: nums2[i], reverse=True)
    result = [0] * len(nums2)

    for i in order:
        if sorted_a[-1] > nums2[i]:
            result[i] = sorted_a.pop()
        else:
            result[i] = sorted_a.popleft()

    return result

Let's trace through the key decisions:

• sorted_a = deque([2, 7, 11, 15]) after sorting nums1.
• order = [3, 1, 2, 0] meaning we process nums2 indices in the order of decreasing values: nums2[3]=11, nums2[1]=10, nums2[2]=4, nums2[0]=1.
• For nums2[3]=11: sorted_a[-1]=15 > 11, so pop right. result[3]=15.
• For nums2[1]=10: sorted_a[-1]=11 > 10, so pop right. result[1]=11.
• For nums2[2]=4: sorted_a[-1]=7 > 4, so pop right. result[2]=7.
• For nums2[0]=1: sorted_a[-1]=2 > 1, so pop right. result[0]=2.
• Final result: [2, 11, 7, 15].

Complexity analysis

The greedy matching loop itself is O(n), since each deque operation (pop from left or right) is O(1). Sorting dominates the overall runtime.

Building blocks

This problem is built on 3 reusable patterns that CodeBricks drills independently.

1. Greedy matching with a deque

Sort your resources, then use a deque to pull from either end. Take from the right (strongest) when you can win, and from the left (weakest) when you cannot. This is the Tian Ji racing strategy in code form.

d = deque(sorted(resources))
for target in sorted(targets, reverse=True):
    if d[-1] > target:
        assign(d.pop())
    else:
        sacrifice(d.popleft())

2. Index sorting for position-aware matching

When the result must be placed at specific positions (not just in order), sort the indices of the target array rather than the target values themselves. This lets you fill the result array in the correct positions while processing targets in a different order.

order = sorted(range(len(arr)), key=lambda i: arr[i], reverse=True)
for i in order:
    result[i] = pick_best(arr[i])

3. Exchange argument for greedy correctness

The proof that greedy works here follows a standard template: assume an optimal solution that differs from the greedy. Find two assignments where swapping them does not reduce (and may increase) the total wins. Repeat until the optimal matches the greedy. This exchange argument is the backbone of many greedy correctness proofs.

Edge cases

Before submitting, make sure your solution handles these:

• All elements equal nums1 = [3, 3, 3], nums2 = [3, 3, 3]: no element in nums1 strictly beats any element in nums2. The greedy sacrifices every element. Any arrangement returns 0 wins.
• Already optimal nums1 = [5, 6, 7], nums2 = [1, 2, 3]: every element wins. The greedy assigns nums1 in sorted order. All 3 wins achieved.
• No wins possible nums1 = [1, 2, 3], nums2 = [4, 5, 6]: every element in nums2 is larger. The greedy sacrifices in order. Return any arrangement (0 wins regardless).
• Some wins, some sacrifices nums1 = [2, 7, 11, 15], nums2 = [1, 10, 4, 11]: this is the example from above. The greedy achieves all 4 wins. Not all inputs allow 100% wins, but the greedy always finds the maximum.
• Duplicate values nums1 = [2, 2, 5], nums2 = [1, 2, 3]: nums1[i] must be strictly greater. The two 2s tie with nums2[1]=2, so that match is a sacrifice. Result: 2 wins.

Common mistakes

1. Processing nums2 from smallest to largest. If you match small targets first, you might use a mid-range element to beat a small target, leaving nothing to beat a larger target that a cheaper element could not have handled. Always process from largest to smallest.

2. Using >= instead of > for the win condition. The problem requires strict inequality. Using >= counts ties as wins and produces wrong results. Check sorted_a[-1] > nums2[i], not >=.

3. Forgetting to handle the sacrifice case. When no element can win, you must still assign something. Assigning the smallest remaining element (pop left) minimizes waste. Forgetting this case means some result positions stay at their default value (0), which corrupts the output.

From understanding to recall

You have seen how the greedy deque strategy works: sort nums1, process nums2 from largest to smallest, pop from the right when you can win, pop from the left when you cannot. The code is clean, the reasoning is intuitive, and the time complexity is optimal. But can you write it from scratch in an interview?

The details that trip people up are: sorting the indices (not the values) of nums2, using strict > instead of >=, and remembering to pop from the left (not just skip) when you cannot win. These are exactly the kinds of small errors that cost you under pressure.

Spaced repetition closes that gap. You practice writing the deque-based greedy matching from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize advantage by rearranging" and the code flows out. The greedy deque matching pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems.

Related posts

• Assign Cookies
• Queue Reconstruction by Height
• Task Scheduler
• Two Sum