Advantage Shuffle
Advantage Shuffle is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (sort + two pointers, strongest opponent first), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (smallest winner by scanning) up.
Problem
You are given two integer arrays nums1 and nums2 of the same length. Position i is won when nums1[i] > nums2[i] (a tie does not count).
Rearrange nums1 so that the number of won positions is as large as possible, and return that arrangement. If several arrangements win the maximum number of positions, any one of them is accepted.
Examples
Example 1
- Input
nums1 = [3, 8, 1, 6], nums2 = [5, 2, 7, 0]- Output
[6, 3, 8, 1]- Why
- 6 > 5, 3 > 2, 8 > 7 and 1 > 0, so all four positions are won. Any arrangement that also wins 4 positions is accepted.
Example 2
- Input
nums1 = [4, 4, 4], nums2 = [5, 1, 3]- Output
[4, 4, 4]- Why
- No 4 can beat the 5, so the best possible is winning the other two positions.
Example 3
- Input
nums1 = [10, 2, 7], nums2 = [9, 9, 1]- Output
[10, 2, 7]- Why
- Only 10 beats a 9. The other 9 cannot be beaten, so it gets the 2 as a sacrifice, and 7 beats the 1: 2 positions won.
Constraints
1 <= nums1.length <= 10^5nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (smallest winner by scanning) | O(n²) | O(n) |
| Optimal (sort + two pointers, strongest opponent first) | O(n log n) | O(n) |
1Brute force (smallest winner by scanning)
O(n²)Each of the n positions may scan all n values of nums1.O(n)Used flags, the index order and the result array.Visit the positions of nums2 from the smallest value up. For each, scan the sorted nums1 for the smallest unused value that is strictly larger and assign it. Positions that nothing can beat are filled at the end with whatever values are left over.
- Sort nums1; sort the indices of nums2 by value, ascending.
- For each index i in that order, scan nums1 for the first unused value > nums2[i]; if found, put it at res[i] and mark it used.
- Fill every unassigned res slot with the remaining unused values in any order.
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] a = nums1.clone();
Arrays.sort(a);
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (x, y) -> Integer.compare(nums2[x], nums2[y]));
boolean[] used = new boolean[n];
int[] res = new int[n];
boolean[] filled = new boolean[n];
for (int i : order) {
for (int j = 0; j < n; j++) {
if (!used[j] && a[j] > nums2[i]) {
used[j] = true;
res[i] = a[j];
filled[i] = true;
break;
}
}
}
int j = 0;
for (int i = 0; i < n; i++) {
if (filled[i]) continue;
while (used[j]) j++;
used[j] = true;
res[i] = a[j];
}
return res;
}
}class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
a = sorted(nums1)
order = sorted(range(n), key=lambda x: nums2[x])
used = [False] * n
res = [0] * n
filled = [False] * n
for i in order:
for j in range(n):
if not used[j] and a[j] > nums2[i]:
used[j] = True
res[i] = a[j]
filled[i] = True
break
j = 0
for i in range(n):
if filled[i]:
continue
while used[j]:
j += 1
used[j] = True
res[i] = a[j]
return resclass Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> a(nums1);
sort(a.begin(), a.end());
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
stable_sort(order.begin(), order.end(), [&](int x, int y) { return nums2[x] < nums2[y]; });
vector<bool> used(n, false), filled(n, false);
vector<int> res(n, 0);
for (int i : order) {
for (int j = 0; j < n; j++) {
if (!used[j] && a[j] > nums2[i]) {
used[j] = true;
res[i] = a[j];
filled[i] = true;
break;
}
}
}
int j = 0;
for (int i = 0; i < n; i++) {
if (filled[i]) continue;
while (used[j]) j++;
used[j] = true;
res[i] = a[j];
}
return res;
}
};function advantageCount(nums1, nums2) {
const n = nums1.length;
const a = [...nums1].sort((x, y) => x - y);
const order = [...Array(n).keys()].sort((x, y) => nums2[x] - nums2[y]);
const used = new Array(n).fill(false);
const filled = new Array(n).fill(false);
const res = new Array(n).fill(0);
for (const i of order) {
for (let j = 0; j < n; j++) {
if (!used[j] && a[j] > nums2[i]) {
used[j] = true;
res[i] = a[j];
filled[i] = true;
break;
}
}
}
let j = 0;
for (let i = 0; i < n; i++) {
if (filled[i]) continue;
while (used[j]) j++;
used[j] = true;
res[i] = a[j];
}
return res;
}2Optimal (sort + two pointers, strongest opponent first)
O(n log n)Two sorts, then one linear pass with two pointers.O(n)The index order and the result array.Sort nums1 and process nums2's values from largest to smallest. For the current (largest remaining) opponent, if our largest remaining value beats it, use it: nothing smaller would serve this opponent, and every later opponent is smaller anyway. If even our largest cannot win, no value can, so throw our smallest value at it and keep the strong ones for later.
- Sort nums1 ascending; sort indices of nums2 by value, descending.
- lo = 0, hi = n - 1.
- For each index i in that order: if nums1[hi] > nums2[i], res[i] = nums1[hi--]; else res[i] = nums1[lo++].
- Return res.
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] a = nums1.clone();
Arrays.sort(a);
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (x, y) -> Integer.compare(nums2[y], nums2[x]));
int[] res = new int[n];
int lo = 0, hi = n - 1;
for (int i : order) {
if (a[hi] > nums2[i]) res[i] = a[hi--];
else res[i] = a[lo++];
}
return res;
}
}class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
a = sorted(nums1)
order = sorted(range(n), key=lambda x: -nums2[x])
res = [0] * n
lo, hi = 0, n - 1
for i in order:
if a[hi] > nums2[i]:
res[i] = a[hi]
hi -= 1
else:
res[i] = a[lo]
lo += 1
return resclass Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> a(nums1);
sort(a.begin(), a.end());
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int x, int y) { return nums2[x] > nums2[y]; });
vector<int> res(n);
int lo = 0, hi = n - 1;
for (int i : order) {
if (a[hi] > nums2[i]) res[i] = a[hi--];
else res[i] = a[lo++];
}
return res;
}
};function advantageCount(nums1, nums2) {
const n = nums1.length;
const a = [...nums1].sort((x, y) => x - y);
const order = [...Array(n).keys()].sort((x, y) => nums2[y] - nums2[x]);
const res = new Array(n);
let lo = 0, hi = n - 1;
for (const i of order) {
if (a[hi] > nums2[i]) res[i] = a[hi--];
else res[i] = a[lo++];
}
return res;
}Edge cases to test
- A single element, won or lost
- Ties: an equal value does not count as beating
- nums1 cannot win anywhere (every value is too small)
- Duplicates in both arrays
- Several arrangements reach the same best count (any of them is accepted)
Hints
Hint 1
Compare it to a card game: when you cannot beat an opponent's card, throw away your weakest card on it.
Hint 2
Handle the opponent's values from largest to smallest. Your largest remaining value either beats the current one or nothing you hold can.
Hint 3
Sort nums1 and keep two pointers: take from the top when it wins, otherwise sacrifice from the bottom.
FAQ
What is the best time complexity for Advantage Shuffle?
Optimal (sort + two pointers, strongest opponent first) runs in O(n log n) time and O(n) extra space. Two sorts, then one linear pass with two pointers.
Which pattern does Advantage Shuffle use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Advantage Shuffle?
Yes. Brute force (smallest winner by scanning) takes O(n²) time and O(n) space. Visit the positions of nums2 from the smallest value up.
Which edge cases should I test for Advantage Shuffle?
A single element, won or lost; Ties: an equal value does not count as beating; nums1 cannot win anywhere (every value is too small); Duplicates in both arrays; Several arrangements reach the same best count (any of them is accepted).