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.
This approach involves sorting the arrays and using a two-pointer technique to maximize the advantage. By sorting, we can easily find which elements can pair to maximize the advantage.
Steps:
nums1 and create an array of indices of nums2 sorted based on values.nums1 to the sorted indices of nums2, ensuring we maximize comparisons where nums1[i] > nums2[i].nums1 and uses two pointers to optimally distribute its elements to maximize advantage. Unsuited elements replace the largest unmatched element from nums2 which minimizes their impact.Time Complexity: O(n log n), primarily due to sorting of arrays.
Space Complexity: O(n), due to the storage of results and sorted indices.
This method involves using a map to store elements of nums1 and using binary search to quickly find the smallest usable element to maximize the advantage.
Steps:
nums1 in a map.nums2, find the smallest greater element from the map to maximize the advantage, using binary search capabilities.nums1 for each element in nums2. Efficient for matching large sets due to logarithmic lookup complexity.Time Complexity: O(n log n), due to sorting and map operations.
Space Complexity: O(n), as we store frequencies in a map.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Sorting and Two Pointers | Time Complexity: O(n log n), primarily due to sorting of arrays. Space Complexity: O(n), due to the storage of results and sorted indices. |
| Approach 2: Optimal Utilization with Map and Binary Search | Time Complexity: O(n log n), due to sorting and map operations. Space Complexity: O(n), as we store frequencies in a map. |
| Default Approach | — |
| 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. |
Advantage Shuffle | Live Coding with Explanation | Leetcode - 870 • Algorithms Made Easy • 2,525 views views
Watch 9 more video solutions →Practice Advantage Shuffle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor