Watch 10 video solutions for Advantage Shuffle, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by Algorithms Made Easy has 2,525 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integer arrays nums1 and nums2 both of the same length. The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].
Return any permutation of nums1 that maximizes its advantage with respect to nums2.
Example 1:
Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11] Output: [2,11,7,15]
Example 2:
Input: nums1 = [12,24,8,32], nums2 = [13,25,32,11] Output: [24,32,8,12]
Constraints:
1 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109Problem Overview: You are given two arrays of equal length. Rearrange nums1 so that the number of indices where nums1[i] > nums2[i] is maximized. The challenge is deciding which elements should "compete" against each value in nums2 to gain the most wins.
Approach 1: Greedy with Sorting and Two Pointers (O(n log n) time, O(n) space)
This method uses a classic greedy strategy combined with sorting. Sort nums1 in ascending order. Then sort the indices of nums2 by their values. Use two pointers on nums1: one pointing to the smallest element and another to the largest. Iterate through nums2 from its largest value down. If the largest remaining value in nums1 can beat the current nums2 value, assign it and move the right pointer. Otherwise, sacrifice the smallest value in nums1. This greedy choice ensures strong numbers are reserved for winnable comparisons while weaker numbers are used where winning is impossible.
The algorithm performs a single pass after sorting and builds the result array directly. Sorting dominates the runtime, giving O(n log n) time and O(n) extra space for the result and index mapping.
Approach 2: Optimal Utilization with Map and Binary Search (O(n log n) time, O(n) space)
This version maintains an ordered map (such as TreeMap) of available values from nums1. For each element in nums2, perform a binary search to find the smallest number strictly greater than it. If such a value exists, use it and remove it from the map. Otherwise, remove the smallest available number and assign it as a deliberate loss.
The key insight: always use the minimum number that still beats the current value. That preserves larger numbers for future comparisons. Balanced tree operations like insertion, lookup, and removal take O(log n), and since they run for every element, the total complexity is O(n log n) with O(n) space.
This approach is conceptually clean and works well in languages with built-in ordered maps. It highlights the "assign the smallest winning candidate" greedy rule and relies heavily on array iteration plus binary search inside the map.
Recommended for interviews: The greedy sorting + two pointer solution is what most interviewers expect. It shows you recognize the "Tian Ji horse racing" pattern: use strong elements to beat winnable matches and sacrifice weak ones otherwise. The map + binary search method is also acceptable, but the two-pointer approach is simpler and usually preferred during whiteboard discussions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting and Two Pointers | O(n log n) | O(n) | Best general solution. Easy to reason about and commonly expected in interviews. |
| Map with Binary Search (TreeMap) | O(n log n) | O(n) | Useful when an ordered map or multiset is available and binary search on remaining values is convenient. |