870. Advantage Shuffle
Asked at Walmart
Difficulty
Medium
Time
O(n log n)
Space
O(n)
Pattern
Array
Companies
1
Problem
You get two integer arrays, nums1 and nums2, of the same length. The advantage of nums1 over nums2 is the count of positions i where nums1[i] > nums2[i]. The comparison must be strictly greater — equal values do not count as a win.
You may reorder nums1 in any way you like. nums2 must stay exactly as it is. Return any permutation of nums1 that gives the largest possible advantage. If several permutations tie, any one of them is accepted.
Think of it as a card game: nums2 is the opponent's fixed hand, and you want to line up your cards so you beat as many of theirs as possible.
Line up your cards to beat the opponent
Constraints
- ●
1 <= nums1.length <= 10^5 - ●
nums2.length == nums1.length - ●
0 <= nums1[i], nums2[i] <= 10^9
Examples
nums1 = [2,7,11,15], nums2 = [1,10,4,11][2,11,7,15]nums1 = [12,24,8,32], nums2 = [13,25,32,11][24,32,8,12]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: try all permutations of nums1 against nums2. That's O(n!) - completely impractical. We need a greedy strategy.
Key insight: sort both arrays. For each element in nums2 (from largest to smallest), assign the smallest element in nums1 that beats it. If no element can beat it, assign the smallest remaining element as a sacrifice.
Why this greedy works: by matching the smallest winning element against each opponent, you preserve larger elements for harder opponents. This is the optimal strategy - it never wastes a big element on an easy win.
Implementation: sort nums1 ascending. Sort nums2 with indices. Use two pointers on nums1 (lo=0, hi=n-1) and iterate nums2 from largest to smallest. If nums1[hi] > nums2[j], assign nums1[hi] (win). Otherwise assign nums1[lo] (sacrifice).
Edge cases: all elements in nums1 are smaller than nums2 (all sacrifices), all elements in nums1 are larger (all wins), equal values (not a win - need strictly greater).
Optimal Approach
Step 1: Sort nums1. Sort nums2 with original indices.
Step 2: Initialize lo = 0, hi = n-1 on nums1.
Step 3: Iterate nums2 from largest to smallest:
- If nums1[hi] > nums2[j] element: assign nums1[hi] to that position (win). Decrement hi.
- Otherwise: assign nums1[lo] to that position (sacrifice). Increment lo.
Step 4: Place assigned values back into the result array at the original indices of nums2.
Walkthrough with nums1 = [2,7,11,15] nums2 = [1,10,4,11]:
- Sort nums1: [2,7,11,15].
- Sorted nums2: [(1,0), (4,2), (10,1), (11,3)].
- Largest nums2=11: 15>11, win. result[3]=15.
- nums2=10: 11>10, win. result[1]=11.
- nums2=4: 7>4, win. result[2]=7.
- nums2=1: 2>1, win. result[0]=2.
- Result: [2,7,11,15].
Time: O(n log n) for sorting. Space: O(n) for the result array.
Greedy: biggest opponent first
What Trips People Up in Real Interviews
Trying to sort both arrays and compare element-by-element. That does not maximize wins - you need to match each nums2 element against the best available nums1 element.
Forgetting that equal values are not wins. The condition is strictly greater: nums1[i] > nums2[i]. If nums1[i] == nums2[i], it is not an advantage.
Assigning the largest nums1 element to the smallest nums2 element. That wastes big elements. Instead, assign the smallest winning element to each nums2 element to preserve big ones for tough opponents.
Losing track of original indices. After sorting nums2, you must remember where each element came from so you can place the assigned value at the correct position in the result.
Not handling the sacrifice case. When no element in nums1 can beat the current nums2 element, assign the smallest remaining element. It will lose anyway, so sacrifice it and save bigger elements for winnable matchups.
Solution Code
O(n log n) timedef advantageCount(nums1, nums2):
nums1.sort()
sorted_nums2 = sorted((v, i) for i, v in enumerate(nums2))
result = [0] * len(nums1)
lo, hi = 0, len(nums1) - 1
for val, idx in reversed(sorted_nums2):
if nums1[hi] > val:
result[idx] = nums1[hi]
hi -= 1
else:
result[idx] = nums1[lo]
lo += 1
return resultFrequently Asked Questions
What is the Advantage Shuffle problem?
Given two arrays nums1 and nums2 of equal length, rearrange nums1 to maximize the number of positions where nums1[i] > nums2[i]. If not possible, put any remaining elements there. This is a greedy matching problem that tests your ability to optimize element assignment.
How do you solve Advantage Shuffle?
The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Advantage Shuffle?
Advantage Shuffle is asked at Walmart. It is a medium difficulty problem.
What are common mistakes on Advantage Shuffle?
- Trying to sort both arrays and compare element-by-element. That does not maximize wins - you need to match each nums2 element against the best available nums1 element.
- Forgetting that equal values are not wins. The condition is strictly greater: nums1[i] > nums2[i]. If nums1[i] == nums2[i], it is not an advantage.
- Assigning the largest nums1 element to the smallest nums2 element. That wastes big elements. Instead, assign the smallest winning element to each nums2 element to preserve big ones for tough opponents.
- Losing track of original indices. After sorting nums2, you must remember where each element came from so you can place the assigned value at the correct position in the result.
- Not handling the sacrifice case. When no element in nums1 can beat the current nums2 element, assign the smallest remaining element. It will lose anyway, so sacrifice it and save bigger elements for winnable matchups.