{x}
blog image

Advantage Shuffle

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 maximizes its advantage with respect to nums2.

 

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 <= 105
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 109

Solution Explanation for Advantage Shuffle

The problem asks to find a permutation of nums1 that maximizes the advantage over nums2. The advantage is defined as the number of indices where nums1[i] > nums2[i]. This can be solved efficiently using a greedy approach combined with sorting.

Approach:

  1. Sort: Sort both nums1 (ascending) and create a sorted array of pairs (nums2[i], i) (ascending by nums2[i]). The pairs keep track of the original index in nums2.

  2. Two Pointers: Use two pointers, i and j. i points to the smallest element in the sorted nums2 (from the pair array). j points to the largest element in the sorted nums1.

  3. Greedy Assignment: Iterate through nums1. For each element v in nums1:

    • If v > t[i][0] (where t[i][0] is the value of nums2 at index i and t is the sorted array of pairs), it means we can use v to beat the current smallest element in nums2. Assign v to the position t[i][1] (the original index in nums2). Increment i.
    • Otherwise, v is smaller than or equal to the smallest remaining element in nums2. We assign it to the position t[j][1] (the original index of the largest element in nums2 that's still unassigned). Decrement j. This strategy minimizes the damage when we cannot win.

  4. Return: The resulting ans array is a permutation of nums1 that maximizes the advantage.

Time Complexity Analysis:

  • Sorting nums1 and creating the sorted pairs array t takes O(N log N) time, where N is the length of the arrays.
  • The two-pointer iteration takes O(N) time.
  • Therefore, the overall time complexity is dominated by sorting, resulting in O(N log N).

Space Complexity Analysis:

  • We use extra space to store the sorted pairs array t and the ans array. Both have size O(N).
  • Therefore, the space complexity is O(N).

Code Examples (Python, Java, C++, Go, TypeScript, Rust): The provided code snippets in the different languages all implement this approach. They differ slightly in syntax and data structures, but the underlying algorithm remains the same. The comments in each code snippet should make it easy to follow the steps of the algorithm. The Python and Java examples were already provided in your question, I have added more.

This solution efficiently finds a permutation of nums1 that maximizes the advantage against nums2 with optimal time and space complexity.