We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Advantage Shuffle

Number: 901

Difficulty: Medium

Paid? No

Companies: Amazon, Point72

Problem Description

Given two integer arrays nums1 and nums2 of the same length, rearrange (permute) nums1 such that the number of indices i where nums1[i] > nums2[i] is maximized. Return any permutation of nums1 that achieves this maximum advantage.

Key Insights

  • Sort nums1 so you can greedily pick the smallest or largest values as needed.
  • Sort nums2 along with their original indices to preserve ordering of results.
  • Use a two-pointers strategy: assign the largest nums1 value that can beat the current largest nums2 value; if not, assign the smallest available nums1 value to sacrifice the matchup.
  • This greedy approach ensures optimal pairing to maximize the advantage count.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the arrays
Space Complexity: O(n) for auxiliary arrays used to store indices and results

Solution

First, sort nums1 and create a sorted version of nums2 that contains both values and their original indices. Then, iterate in reverse through the sorted nums2 array while maintaining two pointers on nums1: one (high) starting at the end (largest numbers) and one (low) starting at the beginning (smallest numbers).

  • If the current largest element in nums1 beats the current value in nums2, assign it to win that matchup and decrement the high pointer.
  • Otherwise, assign the smallest available element from nums1 to minimize loss (sacrifice) and increment the low pointer.
    After processing, the result is placed back in the order corresponding to the original indices in nums2.

Code Solutions

# Python solution for Advantage Shuffle

def advantageShuffle(nums1, nums2):
    # Sort nums2 along with original indices
    sorted_nums2 = sorted([(value, index) for index, value in enumerate(nums2)])
    # Sort nums1 to prepare for a greedy matchup
    sorted_nums1 = sorted(nums1)
    # Initialize result array with the same length as nums1
    result = [0] * len(nums1)
    # Two pointers for nums1: low for smallest values, high for largest values
    low, high = 0, len(nums1) - 1

    # Iterate from the largest to smallest value in nums2
    for value, index in reversed(sorted_nums2):
        if sorted_nums1[high] > value:
            # If the largest available value in nums1 can win,
            # place it in the corresponding position of the result
            result[index] = sorted_nums1[high]
            high -= 1
        else:
            # Otherwise, sacrifice the smallest value in nums1
            result[index] = sorted_nums1[low]
            low += 1
    return result

# Example usage:
# print(advantageShuffle([2,7,11,15], [1,10,4,11]))
← Back to All Questions