Advantage Shuffle
MedPrompt
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] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward but computationally expensive approach is to try every possible arrangement of nums1. We can generate all permutations of nums1 and, for each one, calculate the advantage score against nums2. We then return the permutation that gives the maximum score.
Algorithm
- Generate every possible permutation of
nums1. - For each permutation, calculate its "advantage" by comparing it element-wise with
nums2. - Keep track of the permutation that yields the highest advantage score.
- After checking all permutations, return the best one found.
Walkthrough
This method explores the entire solution space by generating all n! permutations of the nums1 array. For each generated permutation, we iterate from i = 0 to n-1 and count how many times permutation[i] > nums2[i]. We maintain a variable to store the maximum advantage found so far and the corresponding permutation. While this guarantees finding an optimal solution, its factorial time complexity makes it infeasible for anything but very small arrays.
// NOTE: This is a conceptual implementation and will time out.// A proper permutation generator for arrays with duplicates would be more complex.class Solution { int maxAdvantage = -1; int[] bestPermutation; public int[] advantageCount(int[] nums1, int[] nums2) { bestPermutation = new int[nums1.length]; permute(nums1, 0, nums2); return bestPermutation; } private void permute(int[] nums, int start, int[] nums2) { if (start >= nums.length) { int currentAdvantage = calculateAdvantage(nums, nums2); if (currentAdvantage > maxAdvantage) { maxAdvantage = currentAdvantage; bestPermutation = nums.clone(); } return; } java.util.Set<Integer> used = new java.util.HashSet<>(); for (int i = start; i < nums.length; i++) { if (used.add(nums[i])) { // Handle duplicates swap(nums, start, i); permute(nums, start + 1, nums2); swap(nums, start, i); // backtrack } } } private int calculateAdvantage(int[] p, int[] nums2) { int count = 0; for (int i = 0; i < p.length; i++) { if (p[i] > nums2[i]) { count++; } } return count; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Complexity
Time
O(n! * n) - There are `n!` permutations of `nums1`. For each permutation, we take `O(n)` time to calculate its advantage. This is prohibitively slow.
Space
O(n) - The space is dominated by the recursion stack depth for permutation generation and storing the best permutation found, both of which are proportional to `n`.
Trade-offs
Pros
Guaranteed to find the optimal solution.
Conceptually simple to understand.
Cons
Extremely inefficient due to the factorial time complexity.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
Impractical for the given constraints (
nup to 10^5).
A more refined approach is to use a greedy strategy. For each element in nums2, we try to find the best possible number from nums1 to assign to it. The "best" number is the smallest one that is still larger than the nums2 element, as this saves our larger numbers for tougher opponents. If we can't beat the nums2 element, we use our smallest available number from nums1 as a sacrifice.
Algorithm
- Sort
nums1in ascending order and place its elements into a list for efficient removal. - Initialize an empty result array
ans. - Iterate through
nums2fromi = 0ton-1. - For each
nums2[i], search for the smallest element in the list of availablenums1numbers that is strictly greater thannums2[i]. - If such an element is found, place it in
ans[i]and remove it from the list. - If no such element is found, it's impossible to gain an advantage at index
i. Place the smallest available element fromnums1(a "throwaway" number) inans[i]and remove it from the list. - Return the
ansarray.
Walkthrough
This greedy approach improves upon brute force by making a locally optimal choice at each step. We first sort nums1 to easily find the smallest or smallest-greater elements. We then iterate through nums2 in its original order. For each nums2[i], we need to pick a number from the available numbers in nums1. The best strategy is to pick the smallest number that can beat nums2[i]. This can be found efficiently using binary search on the sorted list of available nums1 numbers. If no number can beat nums2[i], we must lose. To save our better cards for other positions, we sacrifice our weakest available card (the smallest number overall). The main performance bottleneck is removing an element from the list (an ArrayList in Java), which takes linear time in the size of the list, leading to an overall quadratic time complexity.
import java.util.*; class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; List<Integer> sortedNums1 = new ArrayList<>(); for (int num : nums1) { sortedNums1.add(num); } Collections.sort(sortedNums1); int[] result = new int[n]; for (int i = 0; i < n; i++) { int target = nums2[i]; // Binary search to find the smallest element > target int low = 0, high = sortedNums1.size() - 1; int bestChoiceIdx = -1; while(low <= high){ int mid = low + (high - low) / 2; if(sortedNums1.get(mid) > target){ bestChoiceIdx = mid; high = mid - 1; } else { low = mid + 1; } } if (bestChoiceIdx != -1) { // If a winning number is found, use the smallest one result[i] = sortedNums1.get(bestChoiceIdx); sortedNums1.remove(bestChoiceIdx); // O(n) operation } else { // Otherwise, use the smallest available number as a sacrifice result[i] = sortedNums1.get(0); sortedNums1.remove(0); // O(n) operation } } return result; }}Complexity
Time
O(n^2) - Sorting `nums1` takes `O(n log n)`. The main loop runs `n` times. Inside the loop, binary search takes `O(log n)`, but removing an element from an `ArrayList` takes `O(n)` time in the worst case. This makes the total complexity `O(n * n) = O(n^2)`.
Space
O(n) - We need a list to store the elements of `nums1`, which takes `O(n)` space. The result array also takes `O(n)` space.
Trade-offs
Pros
Implements a correct greedy logic.
Much more efficient than the brute-force approach.
Cons
The time complexity is
O(n^2)due to the removal of elements from the list inside the loop.This will likely result in a 'Time Limit Exceeded' error for the given constraints.
This is an optimal greedy approach that uses sorting and a two-pointer technique. The core idea is to match our strongest available number from nums1 against the strongest opponent in nums2. If we can win, we take the advantage. If we can't, we know our strongest number is not strong enough, so we sacrifice our weakest number against this unbeatable opponent, saving our strongest number for a weaker opponent it might be able to beat.
Algorithm
- Sort
nums1in ascending order. - Create a data structure (e.g., a 2D array) to store pairs of
(value, original_index)fornums2, and sort it by value in ascending order. - Initialize an empty result array
ansof sizen. - Use two pointers for the sorted
nums1:lowstarting at0andhighstarting atn-1. - Iterate through the sorted
nums2from the largest element to the smallest. - In each step, consider the strongest remaining opponent from
nums2. - Compare it with our strongest available card from
nums1(atnums1[high]). - If
nums1[high]can beat the opponent, assignans[original_index] = nums1[high]and decrementhigh. - If
nums1[high]cannot beat the opponent, we must sacrifice a card. To save our stronger cards, we sacrifice our weakest card,nums1[low]. Assignans[original_index] = nums1[low]and incrementlow. - After the loop, return the
ansarray.
Walkthrough
To implement this efficiently, we sort nums1 in ascending order. Since we need to place the results back in an array corresponding to the original nums2, we can't sort nums2 directly. Instead, we create a structure (like a 2D array or a custom class) to hold both the value and original index of each element in nums2, and then sort this structure.
We then use two pointers, low and high, on the sorted nums1 array, pointing to the weakest and strongest available numbers, respectively. We iterate through our sorted nums2 structure from the strongest opponent downwards. For each opponent, we check if our strongest card (nums1[high]) can win. If it can, we use it and move to our next strongest card (high--). If it cannot, we must lose this matchup. To maximize our chances elsewhere, we use our weakest, "throwaway" card (nums1[low]) and move to our next weakest card (low++). The result is placed in the final answer array at the opponent's original index.
import java.util.Arrays;import java.util.Comparator; class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; // Sort nums1 in ascending order Arrays.sort(nums1); // Create a 2D array to store nums2 elements with their original indices int[][] sortedNums2 = new int[n][2]; for (int i = 0; i < n; i++) { sortedNums2[i][0] = nums2[i]; sortedNums2[i][1] = i; } // Sort sortedNums2 based on values in ascending order Arrays.sort(sortedNums2, Comparator.comparingInt(a -> a[0])); int[] result = new int[n]; // Pointers for nums1 int low = 0; int high = n - 1; // Iterate through sortedNums2 from strongest opponent to weakest for (int i = n - 1; i >= 0; i--) { int originalIndex = sortedNums2[i][1]; int opponentValue = sortedNums2[i][0]; // If our strongest card can beat their strongest opponent, use it. if (nums1[high] > opponentValue) { result[originalIndex] = nums1[high]; high--; } else { // Otherwise, sacrifice our weakest card. result[originalIndex] = nums1[low]; low++; } } return result; }}Complexity
Time
O(n log n) - The dominant operations are sorting `nums1` and `sortedNums2`, both of which take `O(n log n)`. The final two-pointer traversal takes `O(n)` time.
Space
O(n) - We need `O(n)` space for the `sortedNums2` structure that stores values and original indices. The result array also requires `O(n)` space.
Trade-offs
Pros
Highly efficient with
O(n log n)time complexity.Correctly implements the optimal greedy strategy.
Passes all constraints.
Cons
Requires extra space (
O(n)) to store the sorted version ofnums2along with its original indices.
Solutions
Solution
class Solution {public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; int[][] t = new int[n][2]; for (int i = 0; i < n; ++i) { t[i] = new int[]{nums2[i], i}; } Arrays.sort(t, (a, b)->a[0] - b[0]); Arrays.sort(nums1); int[] ans = new int[n]; int i = 0, j = n - 1; for (int v : nums1) { if (v <= t[i][0]) { ans[t[j--][1]] = v; } else { ans[t[i++][1]] = v; } } return ans; }}class Solution {public: vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2) { int n = nums1.size(); vector<pair<int, int>> t; for (int i = 0; i < n; ++i) t.push_back({nums2[i], i}); sort(t.begin(), t.end()); sort(nums1.begin(), nums1.end()); int i = 0, j = n - 1; vector<int> ans(n); for (int v : nums1) { if (v <= t[i].first) ans[t[j--].second] = v; else ans[t[i++].second] = v; } return ans; }};class Solution: def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1 . sort() t = sorted((v, i) for i, v in enumerate(nums2)) n = len(nums2) ans = [0] * n i, j = 0, n - 1 for v in nums1: if v <= t[i][0]: ans[t[j][1]] = v j -= 1 else: ans[t[i][1]] = v i += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.