Advantage Shuffle
Problem
Given two integer arrays nums1 and nums2 of equal length, permute nums1 so that the number of indices i with nums1[i] > nums2[i] is as large as possible. Return any such permutation.
nums1 = [2,7,11,15], nums2 = [1,10,4,11][2,11,7,15]def advantage_count(nums1, nums2):
s1 = sorted(nums1)
idx = sorted(range(len(nums2)), key=lambda i: -nums2[i])
res = [0] * len(nums1)
lo, hi = 0, len(s1) - 1
for i in idx:
if s1[hi] > nums2[i]:
res[i] = s1[hi]; hi -= 1
else:
res[i] = s1[lo]; lo += 1
return resfunction advantageCount(nums1, nums2) {
const s1 = [...nums1].sort((a, b) => a - b);
const idx = nums2.map((_, i) => i).sort((a, b) => nums2[b] - nums2[a]);
const res = new Array(nums1.length);
let lo = 0, hi = s1.length - 1;
for (const i of idx) {
if (s1[hi] > nums2[i]) res[i] = s1[hi--];
else res[i] = s1[lo++];
}
return res;
}int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] s1 = nums1.clone();
Arrays.sort(s1);
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> nums2[b] - nums2[a]);
int[] res = new int[n];
int lo = 0, hi = n - 1;
for (int i : idx) {
if (s1[hi] > nums2[i]) res[i] = s1[hi--];
else res[i] = s1[lo++];
}
return res;
}vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> s1 = nums1;
sort(s1.begin(), s1.end());
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b){ return nums2[a] > nums2[b]; });
vector<int> res(n);
int lo = 0, hi = n - 1;
for (int i : idx) {
if (s1[hi] > nums2[i]) res[i] = s1[hi--];
else res[i] = s1[lo++];
}
return res;
}Explanation
This is the classic "advantage" greedy, sometimes called the horse-race trick. We want to win as many matchups as possible, where winning at index i means our number beats nums2[i]. The smart move is to spend our strongest cards only where they are truly needed.
We sort our own numbers (s1) and look at the opponents from strongest to weakest (idx sorts indices by descending nums2 value). We keep two pointers into s1: hi at our biggest card, lo at our smallest.
For each opponent we ask: can our current biggest card beat them? If yes (s1[hi] > nums2[i]), we use it and move hi down. If even our biggest card cannot win, that opponent is unbeatable, so we "throw away" our weakest card against them using lo and move lo up. Either way the result is stored at the original index i.
Why it works: a card we cannot use to win is wasted no matter where it goes, so sacrificing our smallest card there preserves stronger cards for winnable matchups.
Example: nums1=[2,7,11,15], nums2=[1,10,4,11]. Sorted ours is [2,7,11,15]. Against 11 our 15 wins; against 10 our 11 wins; against 4 our 7 wins; against 1 we dump 2 — giving [2,11,7,15].