#870

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Advantage Shuffle

Maximize the advantage of nums1 over nums2 using a two-pointer greedy strategy, carefully tracking which elements beat others.

array two pointers greedy sorting

Problem Statement

You are given two integer arrays nums1 and nums2 of equal length. Define the advantage of nums1 over nums2 as the number of indices i where nums1[i] > nums2[i]. The goal is to reorder nums1 to maximize this advantage against nums2.

Return any permutation of nums1 that achieves the maximum possible advantage. For example, given nums1 = [2,7,11,15] and nums2 = [1,10,4,11], a correct output is [2,11,7,15]. Constraints: both arrays have lengths up to 105, and array elements are non-negative integers not exceeding 109.

Examples

Example 1

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

Output: [2,11,7,15]

Example details omitted.

Example 2

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

Output: [24,32,8,12]

Example details omitted.

Constraints

1 <= nums1.length <= 105
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 109

Solution Approach

Sort both arrays

Start by sorting nums1 in ascending order and maintaining the original indices of nums2 sorted by value. This sets up the two-pointer mechanism to assign the smallest nums1 that can beat each nums2 element.

Two-pointer greedy assignment

Use two pointers: one at the start of nums1 and one at the start of the sorted nums2. If the current nums1 element can beat the nums2 element, assign it; otherwise, store it for later. This invariant ensures every advantageous assignment is captured.

Fill remaining positions

Assign the remaining nums1 elements to any leftover nums2 positions where no advantage is possible. This avoids wasting stronger elements and preserves the advantage count established by previous greedy assignments.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

Sorting nums1 and nums2 requires O(N log N) time, and the two-pointer assignment passes over the arrays once, resulting in O(N) space for tracking indices and leftover elements.

What Interviewers Usually Probe

Expect clarification on how to match nums1 elements to nums2 efficiently using sorting.
Be ready to explain why a naive greedy from largest to largest might fail on certain permutations.
Demonstrate understanding of invariant tracking during two-pointer scanning to preserve advantage counts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to preserve original indices of nums2 while sorting, leading to misaligned assignments.
Assigning largest nums1 elements too early, wasting them on nums2 elements that could be beaten by smaller nums1.
Failing to handle leftover nums1 elements correctly, which can reduce the overall advantage count.

Follow-up variants

Compute the minimum permutation of nums1 that still maximizes advantage instead of any permutation.
Apply the same two-pointer greedy pattern to a circular array variant where comparisons wrap around.
Change the condition to nums1[i] >= nums2[i] and adjust the greedy assignment accordingly.

FAQ

What is the key pattern to solve Advantage Shuffle?

The main pattern is two-pointer scanning with invariant tracking, assigning the smallest nums1 that can beat a given nums2 element.

Can multiple outputs be correct?

Yes, any permutation of nums1 that maximizes the number of indices where nums1[i] > nums2[i] is valid.

What is the time complexity of this solution?

Sorting dominates the runtime with O(N log N), while the two-pointer assignment is O(N) in both time and space.

Why can't we always match the largest nums1 to the largest nums2?

Matching largest to largest may waste stronger nums1 elements on nums2 elements that could have been beaten by smaller nums1, reducing overall advantage.

How does GhostInterview ensure correctness?

It tracks indices and leftover assignments, highlighting each step of the two-pointer greedy process to maximize the advantage reliably.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        t = sorted((v, i) for i, v in enumerate(nums2))
        n = len(nums2)
        ans = [0] * n
        i, j = 0, n - 1
        for v in nums1:
            if v <= t[i][0]:
                ans[t[j][1]] = v
                j -= 1
            else:
                ans[t[i][1]] = v
                i += 1
        return ans

Continue Practicing

#881 boats to save people #826 most profit assigning work #948 bag of tokens