Advantage Shuffle
Medium · Greedy · Array · Two Pointers · Greedy · Sorting
Problem
You are given two integer arrays nums1 and nums2 of the same length. The *advantage* of nums1 over nums2 is the number of indices i with nums1[i] > nums2[i].
Return any permutation of nums1 that maximizes its advantage over nums2. nums2 keeps its order; only nums1 is rearranged. Any arrangement with the largest possible advantage is accepted.
Examples
Input: nums1 = [3,8,1,6], nums2 = [5,2,7,4] Output: [6,3,8,1]
6 > 5, 3 > 2 and 8 > 7 give an advantage of 3. The 1 beats nothing, so 4 is out of reach. Any other arrangement with advantage 3 is accepted too.
Input: nums1 = [5,5,1], nums2 = [4,9,6] Output: [5,1,5]
No value of nums1 beats 9 or 6, so only the 4 can be beaten: the best advantage is 1.
Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11] Output: [2,11,7,15]
2 > 1, 11 > 10, 7 > 4 and 15 > 11.
Constraints
- 1 <= len(nums1) <= 10^5
- len(nums2) == len(nums1)
- 0 <= nums1[i], nums2[i] <= 10^9
Approaches
- Baseline: smallest winning card for each opponent — time O(n²), space O(n)
Follow-up
This is the strategy behind the Tian Ji horse race from ancient China: lose your worst horse to their best, then win the rest. What changes if ties also earned something, for example half a point?
Related problems
Start free on Cariara · Coding problems · System design studio
