Advantage Shuffle — Greedy Sun Tzu Strategy [LC 870]

Problem Statement#

Given two arrays nums1 and nums2 of the same length, rearrange nums1 to maximize the number of indices where nums1[i] > nums2[i]. Return any valid rearrangement.

Constraints:

• 1 <= nums1.length <= 10^5
• nums1.length == nums2.length
• 0 <= nums1[i], nums2[i] <= 10^9

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

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

Why This Problem Matters#

LeetCode 870 is a classic FAANG greedy problem from Google and Amazon. It is nicknamed the "Sun Tzu strategy" after the ancient Chinese principle: "fight where you can win, avoid fighting where you cannot." The greedy structure — face the hardest opponent with your weakest when you know you'll lose — is elegant and non-obvious.

The problem tests understanding of two-pointer greedy against a sorted opponent, combined with correctly restoring the answer in the original positions. It is a great follow-up to simpler assignment problems like Assign Cookies (LC 455).

The Core Insight#

The strategy:

1. Sort nums2 by value (with original indices to restore positions)
2. Sort nums1 with two pointers: lo (smallest available) and hi (largest available)
3. For each of B's values from largest to smallest:
   • If your largest (nums1[hi]) can beat B's current value: assign it, move hi left
   • Otherwise: assign your weakest (nums1[lo]) as a sacrifice — you lose this battle but preserve strong elements for later, move lo right
4. Place each assignment back into the original position of B's element

Why face hardest opponents first? If we cannot beat B's strongest, we minimize the loss by sacrificing our weakest element. If we can beat B's strongest, we use just enough to win (our largest, to preserve the advantage of smaller winning elements for less demanding opponents).

Visual Dry Run#

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

Sort nums1: [2, 7, 11, 15] Sort nums2 with indices: [(1,0), (4,2), (10,1), (11,3)] — sorted by value

Process from largest B to smallest (right to left in sorted B):

Result: ans = [2, 11, 7, 15]

Solution (Optimal)#

class Solution:
    def advantageCount(self, nums1, nums2):
        nums1.sort()
        sorted_b = sorted(enumerate(nums2), key=lambda x: -x[1])  # sort B descending by value
        ans = [0] * len(nums1)
        lo, hi = 0, len(nums1) - 1
        for idx, b_val in sorted_b:
            if nums1[hi] > b_val:
                ans[idx] = nums1[hi]
                hi -= 1
            else:
                ans[idx] = nums1[lo]
                lo += 1
        return ans

var advantageCount = function(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    const sortedB = nums2.map((v, i) => [v, i]).sort((a, b) => b[0] - a[0]);
    const ans = new Array(nums1.length);
    let lo = 0, hi = nums1.length - 1;
    for (const [bVal, idx] of sortedB) {
        if (nums1[hi] > bVal) {
            ans[idx] = nums1[hi--];
        } else {
            ans[idx] = nums1[lo++];
        }
    }
    return ans;
};

Time: O(n log n) — sorting dominates Space: O(n) — sortedB array and answer array

Common Mistakes#

• Not restoring the answer to the original positions of nums2 — must track original indices in sortedB
• Sorting nums2 without preserving indices — loses the mapping back to the output array
• Using a greedy from smallest instead of largest — starting from B's smallest first is suboptimal
• Not handling ties correctly — when nums1[hi] == b_val, we cannot win; sacrifice lo
• Forgetting that the answer can use any rearrangement — the output position follows B's original indices

Interview Tips#

• Explain the Sun Tzu intuition: "use your weakest when you can't win to preserve your strongest for later"
• Walk through the two-pointer update: hi decrements when we win, lo increments when we sacrifice
• Clarify why we process B in descending order: "we handle the toughest opponents first"
• Mention the original index tracking: "we need to put each answer in B's original position, so we track (value, index) pairs"
• Compare to Assign Cookies (LC 455): similar greedy matching but simpler since cookies don't need original position tracking

Follow-up Questions#

• What if you want to minimize the advantage instead of maximize? (Greedy: against each of B's weakest, send your strongest if it loses; otherwise your weakest winner)
• What if each element of B can be beaten multiple times (not a one-to-one matching)? (Becomes a different problem — use each A element for the best available B)
• Can there be multiple optimal arrangements? (Yes — the problem asks for any valid maximum-advantage arrangement)
• How does this relate to Assign Cookies (LC 455)? (Same greedy matching structure; 455 doesn't require restoring original positions)
• What if B's elements have duplicate values? (The algorithm handles it — sort by value, identical values are processed the same way)

Key Takeaways#

• LeetCode 870 is asked at Google and Amazon — Sun Tzu greedy: sacrifice weakest when you cannot win, use just enough when you can
• Sort nums1 ascending; sort nums2 descending by value (keeping original indices)
• Two pointers lo and hi on sorted nums1: use hi (strongest) if it beats current B; use lo (weakest) as sacrifice otherwise
• Always process B's elements from strongest to weakest — this guarantees the greedy is globally optimal
• Time O(n log n), Space O(n) — sorting plus index tracking arrays
• The key implementation detail: track (value, original_index) pairs for B to restore the answer at correct positions
• Pattern generalizes to any "match arrays to maximize wins" problem — the same greedy applies