LeetCode 870: Advantage Shuffle

Problem Description

LeetCode Problem 870

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

Difficulty: Medium

Tags: array, two pointers, greedy, sorting

Rating: 94.28%

Solution Approach

1. First, we sort nums1 to have our numbers in ascending order
2. For nums2, we create pairs of (number, original_index) and sort them
3. We use two pointers to track:
   • The smallest unused number in nums1 (left pointer)
   • The largest unused number in nums1 (right pointer)
4. For each number in nums2 (starting from largest):
   • If our largest remaining number can beat it, use that
   • Otherwise, use our smallest number (essentially giving up on that position)

Detailed Walkthrough

Let’s walk through Example 1: nums1 = [2,7,11,15], nums2 = [1,10,4,11]

1. Sort nums1: [2,7,11,15]

2. Create and sort indexed nums2:

   Original:     [(1,0), (10,1), (4,2), (11,3)]
   After sort:   [(1,0), (4,2), (10,1), (11,3)]
   

3. Process from largest to smallest in nums2:

   • For 11: Use 15 (our largest) → result[3] = 15
   • For 10: Use 11 → result[1] = 11
   • For 4: Use 7 → result[2] = 7
   • For 1: Use 2 → result[0] = 2

Final result: [2,11,7,15]

Implementation

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        nums1.sort()
        
        indexed_nums2 = [(n, i) for i, n in enumerate(nums2)]
        indexed_nums2.sort()
        
        res = [0] * n
        
        # Two pointers for nums1
        l = 0    # Points to smallest unused number
        r = n-1  # Points to largest unused number
        
        # Process nums2 from largest to smallest
        for i in range(n-1, -1, -1):
            num, idx = indexed_nums2[i]
            if nums1[r] > num:
                # If our largest can beat it, use it
                res[idx] = nums1[r]
                r -= 1
            else:
                # Otherwise, use our smallest
                res[idx] = nums1[l]
                l += 1
        
        return res

Complexity Analysis

• Time Complexity: $O(n log n)$ due to sorting both arrays
• Space Complexity: $O(n)$ to store the indexed version of nums2 and result array