Advantage Shuffle — Editorial

Opening the reading…

Intuitionwhy every winning assignment can be protected

A value in nums1 creates one point only when it is placed against a larger value in nums2. If the largest unused value in nums1 cannot beat the current target, then no unused value can beat it either. That target is unavoidable, so assigning the smallest unused value loses nothing and saves the larger values for targets they may still beat.

Process nums2 from largest to smallest. When the largest unused nums1 value beats the current target, use it there: giving that win to a smaller value could waste the opportunity. When it does not beat the target, use the smallest unused nums1 value as a sacrifice. Sorting lets two pointers track exactly those two choices, while an index array lets you place each answer back at its original nums2 position.

Approach

Build an array of nums2 indices and sort those indices by their nums2 values, because sorting the values themselves would lose the positions where the answer must be written.

Sort nums1 in ascending order, because the greedy choices need constant-time access to both the smallest and largest unused values.

Set left to 0 and right to n - 1, so every unused nums1 value lies between the two pointers and each value is consumed exactly once.

Visit the sorted nums2 indices from largest target to smallest, because a large target is the hardest remaining target to beat and must be decided before easier targets can use the same values.

If nums1[right] > nums2[idx[i]], place nums1[right] at answer position idx[i] and move right left, because this assignment creates a win without using a smaller value that might also win elsewhere.

Otherwise place nums1[left] at answer position idx[i] and move left right, because even the largest remaining value fails, so the target cannot contribute a win and the smallest sacrifice preserves every larger value.

Return the answer array after all targets are assigned, because every nums1 value has been used once and every assignment was made at the original nums2 position.

Complexitysorting dominates the work for every input shape

MEASURE	BOUND	WHY
Time	O(n log n)	Sorting nums1 and the n-element index array costs O(n log n) each. The assignment loop advances exactly one pointer for every target, so it costs O(n) and does not change the sorting bound.
Space	O(n) extra	The index array and answer array each hold n integers, while the sort operations use at most O(log n) auxiliary stack space. The returned answer is required output and is excluded from the extra-space bound; there is no input shape that makes the linear arrays exceed O(n).

Here n is the common length of nums1 and nums2.

Annotated solutionC++ · greedy with descending targets and two pointers

CPPSort nums1 and the target indices, then assign either the largest winner or the smallest unavoidable sacrifice.

#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);

        sort(idx.begin(), idx.end(), [&](int i, int j) {
            return nums2[i] < nums2[j];
        });
        sort(nums1.begin(), nums1.end());

        vector<int> ans(n);
        int left = 0;
        int right = n - 1;

        for (int i = n - 1; i >= 0; --i) {
            int position = idx[i];
            if (nums1[right] > nums2[position]) {
                ans[position] = nums1[right];
                --right;
            } else {
                ans[position] = nums1[left];
                ++left;
            }
        }

        return ans;
    }
};

The comparison uses nums1[right] rather than searching for a winner. If the largest remaining value wins, it is safe to spend it because the current target is the hardest target still being considered. If it fails, every remaining value fails, so nums1[left] is the only choice that cannot reduce a future win.

The answer is written at ans[position], not at ans[i]. The loop order is the order of sorted target values, but position is the original index in nums2. Keeping those two meanings separate is what makes the returned permutation line up with the input arrays.

The ascending-target alternativesame asymptotic cost, with the greedy choice viewed from the other end

You can process targets from smallest to largest instead. For each target, find the smallest remaining nums1 value that beats it; if none can, spend the largest remaining value as the sacrifice. This is the same exchange idea in reverse: do not waste a large value on an easy target, and do not let an impossible target consume a value that could win later.

CPPProcess the easiest targets first, using the smallest winning value or the largest value when no win exists.

#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);

        sort(nums1.begin(), nums1.end());
        sort(idx.begin(), idx.end(), [&](int i, int j) {
            return nums2[i] < nums2[j];
        });

        vector<int> ans(n);
        int left = 0;
        int right = n - 1;

        for (int i = 0; i < n; ++i) {
            int position = idx[i];
            if (nums1[left] > nums2[position]) {
                ans[position] = nums1[left];
                ++left;
            } else {
                ans[position] = nums1[right];
                --right;
            }
        }

        return ans;
    }
};

This alternative is not an optimization: it still sorts twice, uses O(n) extra space, and runs in O(n log n) time. The descending version often makes the proof more direct because it asks whether the largest remaining value can handle the hardest target. The ascending version is equally valid when thinking in terms of using the smallest possible winner.