title: Advantage Shuffle
slug: advantage-shuffle
difficulty: medium
leetcode_id: 870
leetcode_url: https://leetcode.com/problems/advantage-shuffle/
categories:
  - arrays
  - sorting
patterns:
  - slug: greedy
    is_optimal: false
  - slug: two-pointers
    is_optimal: true

function_signature: "def advantage_count(nums1: list[int], nums2: list[int]) -> list[int]:"

test_cases:
  visible:
    - input: { nums1: [2, 7, 11, 15], nums2: [1, 10, 4, 11] }
      expected: [2, 11, 7, 15]
    - input: { nums1: [12, 24, 8, 32], nums2: [13, 25, 32, 11] }
      expected: [24, 32, 8, 12]
  hidden:
    - input: { nums1: [1], nums2: [1] }
      expected: [1]
    - input: { nums1: [5, 5, 5], nums2: [1, 2, 3] }
      expected: [5, 5, 5]
    - input: { nums1: [1, 2, 3], nums2: [3, 2, 1] }
      expected: [1, 3, 2]
    - input: { nums1: [2, 0, 4, 1, 2], nums2: [1, 3, 0, 0, 2] }
      expected: [2, 4, 1, 2, 0]

description: |
  You are given two integer arrays `nums1` and `nums2` both of the same length. The **advantage** of `nums1` with respect to `nums2` is the number of indices `i` for which `nums1[i] > nums2[i]`.

  Return *any permutation of* `nums1` *that maximises its **advantage** with respect to* `nums2`.

constraints: |
  - `1 <= nums1.length <= 10^5`
  - `nums2.length == nums1.length`
  - `0 <= nums1[i], nums2[i] <= 10^9`

examples:
  - input: "nums1 = [2,7,11,15], nums2 = [1,10,4,11]"
    output: "[2,11,7,15]"
    explanation: "With this arrangement: 2 > 1 (advantage), 11 > 10 (advantage), 7 > 4 (advantage), 15 > 11 (advantage). Total advantage = 4."
  - input: "nums1 = [12,24,8,32], nums2 = [13,25,32,11]"
    output: "[24,32,8,12]"
    explanation: "With this arrangement: 24 > 13 (advantage), 32 > 25 (advantage), 8 < 32 (no advantage), 12 > 11 (advantage). Total advantage = 3, which is optimal."

explanation:
  intuition: |
    This problem is a classic example of the **greedy assignment strategy**, famously known as "Tian Ji's Horse Racing" from ancient Chinese history.

    Imagine you're playing a card game where you must beat your opponent's cards. For each of their cards, you want to use your *smallest card that can still win*. If none of your remaining cards can win, you sacrifice your weakest card to preserve stronger ones for future rounds.

    Think of it like this: if your opponent plays a 10, and you have cards [8, 11, 15], you should play 11 (the smallest winning card), not 15. This preserves 15 for potentially beating a higher card later. If you can't beat their card at all, throw away your weakest card (8) since it's useless anyway.

    The key insight is that **greedily using the smallest winning card** maximises your overall advantage. Sorting both arrays allows us to efficiently find these optimal pairings.

  approach: |
    We solve this using a **Greedy Assignment with Sorting** approach:

    **Step 1: Sort nums1 and create indexed pairs for nums2**

    - Sort `nums1` in ascending order so we can efficiently find the smallest card that beats each opponent
    - Create pairs of `(value, original_index)` for `nums2` and sort by value
    - This lets us process opponents from weakest to strongest while remembering original positions

    &nbsp;

    **Step 2: Use two pointers on sorted nums1**

    - Maintain `left` pointer at start (smallest unused card)
    - Maintain `right` pointer at end (largest unused card)
    - For each opponent value (from smallest to largest):
      - If our smallest card (`nums1[left]`) can beat it, use it and advance `left`
      - Otherwise, sacrifice our smallest card to the opponent's *strongest* remaining position

    &nbsp;

    **Step 3: Build the result array**

    - Process `nums2` values from largest to smallest
    - For each position, assign either a winning card or a sacrificed card
    - The result array is built by placing cards at their corresponding original indices

    &nbsp;

    This greedy approach works because using the smallest winning card is always optimal — it never hurts to save larger cards for potentially harder opponents.

  common_pitfalls:
    - title: Forgetting Original Indices
      description: |
        The output must be a permutation of `nums1` that corresponds to the *original positions* of `nums2`. Simply sorting both arrays and matching them loses track of where each value in `nums2` originally was.

        For example, if `nums2 = [1, 10, 4, 11]`, after sorting we get `[1, 4, 10, 11]`. If we assign values to this sorted order, we need to map them back: position 0 in sorted → position 0 in original, position 1 in sorted → position 2 in original, etc.
      wrong_approach: "Sort both arrays and match directly"
      correct_approach: "Track original indices when sorting nums2"

    - title: Using Largest Card Instead of Smallest Winner
      description: |
        A tempting but suboptimal strategy is to always use your largest card to guarantee a win. This wastes strong cards on weak opponents.

        For example, if `nums1 = [5, 10, 15]` and `nums2 = [3, 8, 14]`:
        - Using largest: 15 beats 3, 10 beats 8, 5 < 14 → 2 wins
        - Using smallest winner: 5 beats 3, 10 beats 8, 15 beats 14 → 3 wins

        Always use the *smallest* card that can still win.
      wrong_approach: "Match largest available to each opponent"
      correct_approach: "Use smallest card that can beat each opponent"

    - title: Sacrificing Wrong Cards
      description: |
        When you can't beat an opponent, you should sacrifice your *weakest* card, not a random one. Weak cards have the least potential for future wins, so throwing them away preserves your winning potential.

        If you can't beat any remaining opponent with your smallest card, that card is essentially worthless — use it against the opponent's strongest value to get it out of the way.
      wrong_approach: "Randomly assign losing cards"
      correct_approach: "Sacrifice smallest card when no win is possible"

  key_takeaways:
    - "**Greedy assignment pattern**: When matching elements from two arrays, use the smallest value that satisfies the condition"
    - "**Sacrifice strategy**: When you can't win, sacrifice your weakest asset to preserve stronger ones"
    - "**Index tracking**: When the output order matters, pair values with their original indices before sorting"
    - "**Classic problem**: This is Tian Ji's Horse Racing strategy — a foundational greedy pattern that appears in many variations"

  time_complexity: "O(n log n). Sorting both arrays dominates the complexity. The two-pointer assignment is O(n)."
  space_complexity: "O(n). We store the sorted `nums1`, indexed pairs for `nums2`, and the result array."

solutions:
  - approach_name: Greedy with Two Pointers
    is_optimal: true
    code: |
      def advantage_count(nums1: list[int], nums2: list[int]) -> list[int]:
          n = len(nums1)
          # Sort nums1 ascending - we'll pick smallest winning cards
          sorted_nums1 = sorted(nums1)

          # Pair nums2 values with original indices, sort by value descending
          # Process strongest opponents first
          indexed_nums2 = sorted(enumerate(nums2), key=lambda x: -x[1])

          result = [0] * n
          left, right = 0, n - 1

          for orig_idx, val in indexed_nums2:
              # Can our largest remaining card beat this opponent?
              if sorted_nums1[right] > val:
                  # Yes - use it (greedy: use strongest when facing strongest)
                  result[orig_idx] = sorted_nums1[right]
                  right -= 1
              else:
                  # No - sacrifice our weakest card here
                  result[orig_idx] = sorted_nums1[left]
                  left += 1

          return result
    explanation: |
      **Time Complexity:** O(n log n) — Dominated by sorting operations.

      **Space Complexity:** O(n) — For the sorted array and indexed pairs.

      We process opponents from strongest to weakest. For each opponent, if our strongest remaining card can beat them, we use it. Otherwise, we sacrifice our weakest card. This ensures we never waste a strong card when a weaker one would suffice, and we throw away cards that have no winning potential.

  - approach_name: Greedy with Multiset
    is_optimal: true
    code: |
      from sortedcontainers import SortedList

      def advantage_count(nums1: list[int], nums2: list[int]) -> list[int]:
          # Use sorted container for efficient removal and search
          available = SortedList(nums1)
          result = []

          for target in nums2:
              # Find index of smallest value greater than target
              idx = available.bisect_right(target)

              if idx < len(available):
                  # Found a winning card - use smallest one that wins
                  result.append(available.pop(idx))
              else:
                  # No card can win - sacrifice the smallest
                  result.append(available.pop(0))

          return result
    explanation: |
      **Time Complexity:** O(n log n) — Each of the n iterations does O(log n) search and removal.

      **Space Complexity:** O(n) — For the sorted container.

      This approach processes `nums2` in its original order, finding the smallest winning card for each position. Using a sorted container allows O(log n) operations for finding and removing elements. This is conceptually cleaner but requires an external library in Python.

  - approach_name: Brute Force with Backtracking
    is_optimal: false
    code: |
      def advantage_count(nums1: list[int], nums2: list[int]) -> list[int]:
          from itertools import permutations

          def count_advantage(perm):
              return sum(1 for a, b in zip(perm, nums2) if a > b)

          best_perm = nums1[:]
          best_count = count_advantage(best_perm)

          # Try all permutations (only feasible for tiny inputs)
          for perm in permutations(nums1):
              count = count_advantage(perm)
              if count > best_count:
                  best_count = count
                  best_perm = list(perm)

          return best_perm
    explanation: |
      **Time Complexity:** O(n! * n) — Checking all n! permutations, each taking O(n) to evaluate.

      **Space Complexity:** O(n) — For storing permutations.

      This brute force approach tries every possible arrangement of `nums1` and picks the one with maximum advantage. While correct, it's completely impractical for n > 10 due to factorial growth. Included to illustrate why greedy optimisation is essential.
