Advantage Shuffle
Asked at Walmart
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.
Asked At
| 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).
Visual walkthrough for nums1 = [2,7,11,15] nums2 = [1,10,4,11]:
Sort nums1: [2,7,11,15]. Sort nums2 with indices: [(0,1),(2,4),(1,10),(3,11)].
Process nums2 largest first:
- nums2=11 (idx 3): nums1[hi]=15 > 11. Win! Assign 15. hi=2.
- nums2=10 (idx 1): nums1[hi]=11 > 10. Win! Assign 11. hi=1.
- nums2=4 (idx 2): nums1[hi]=7 > 4. Win! Assign 7. hi=0.
- nums2=1 (idx 0): nums1[hi]=2 > 1. Win! Assign 2. hi=-1.
Result: [2,7,11,15] mapped to positions [3,2,1,0] = [2,7,11,15].
All 4 positions win.
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.