problemmediumalgorithmsleetcode-870leetcode 870leetcode870

Advantage Shuffle

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 ofnums1 _that maximizes itsadvantage with respect to _nums2.

Examples

Example 1:

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

Example 2:

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

Constraints:

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

Solution

Method 1 – Greedy with Sorting

Intuition

The key idea is to maximize the number of positions where nums1[i] > nums2[i]. By sorting both arrays, we can always try to assign the smallest possible number from nums1 that is still greater than the current number in nums2. If no such number exists, we assign the smallest remaining number from nums1 (which can't beat any remaining nums2).

Approach

  1. Sort nums1 in ascending order.
  2. Pair each element in nums2 with its index and sort these pairs by value.
  3. Use two pointers for nums1: one at the start (l), one at the end (r).
  4. For each value in sorted nums2:
  • If the largest remaining number in nums1 (nums1[r]) is greater than the current nums2 value, assign it and move r left.
  • Otherwise, assign the smallest remaining number (nums1[l]) and move l right.
  1. Place the assigned number in the answer array at the original index of the current nums2 value.

Code

C++
class Solution {
public:
   vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
      int n = nums1.size();
      vector<int> ans(n);
      vector<pair<int, int>> b;
      for (int i = 0; i < n; ++i) b.push_back({nums2[i], i});
      sort(nums1.begin(), nums1.end());
      sort(b.begin(), b.end());
      int l = 0, r = n - 1;
      for (int i = n - 1; i >= 0; --i) {
        if (nums1[r] > b[i].first) {
           ans[b[i].second] = nums1[r--];
        } else {
           ans[b[i].second] = nums1[l++];
        }
      }
      return ans;
   }
};
Java
class Solution {
   public int[] advantageCount(int[] nums1, int[] nums2) {
      int n = nums1.length;
      int[] ans = new int[n];
      int[][] b = new int[n][2];
      for (int i = 0; i < n; ++i) {
        b[i][0] = nums2[i];
        b[i][1] = i;
      }
      Arrays.sort(nums1);
      Arrays.sort(b, (a, c) -> Integer.compare(a[0], c[0]));
      int l = 0, r = n - 1;
      for (int i = n - 1; i >= 0; --i) {
        if (nums1[r] > b[i][0]) {
           ans[b[i][1]] = nums1[r--];
        } else {
           ans[b[i][1]] = nums1[l++];
        }
      }
      return ans;
   }
}
Python
class Solution:
   def advantageCount(self, nums1: list[int], nums2: list[int]) -> list[int]:
      n = len(nums1)
      ans: list[int] = [0] * n
      b: list[tuple[int, int]] = [(v, i) for i, v in enumerate(nums2)]
      nums1.sort()
      b.sort()
      l, r = 0, n - 1
      for i in range(n - 1, -1, -1):
        if nums1[r] > b[i][0]:
           ans[b[i][1]] = nums1[r]
           r -= 1
        else:
           ans[b[i][1]] = nums1[l]
           l += 1
      return ans

Complexity

  • ⏰ Time complexity: O(N log N) (due to sorting)
  • 🧺 Space complexity: O(N) (for auxiliary arrays)

Comments