Advantage Shuffle [Medium] — Greedy Strongest Beat Weakest

Problem Statement

Given nums and B, rearrange nums to maximize the number of indices where nums[i] > B[i].

Input: nums=[2,7,11,15], B=[1,10,4,11] → Output: [2,11,7,15]

Intuition

Sort nums. Sort B by value (keeping original indices). Use two pointers on sorted nums: if smallest nums can beat smallest remaining B element, assign it; otherwise assign it to the largest B element (sacrifice).

Solutions

C++

vector<int> advantageCount(vector<int>& A, vector<int>& B) {
    sort(A.begin(),A.end());
    int n=B.size();
    vector<int> res(n), idxB(n);
    iota(idxB.begin(),idxB.end(),0);
    sort(idxB.begin(),idxB.end(),[&](int i,int j){return B[i]<B[j];});
    int lo=0,hi=n-1;
    for(int a:A){
        if(a>B[idxB[lo]]) res[idxB[lo++]]=a;
        else               res[idxB[hi--]]=a;
    }
    return res;
}

Python

import sortedcontainers

def advantageCount(nums: list[int], B: list[int]) -> list[int]:
    from sortedcontainers import SortedList
    sl = SortedList(nums)
    res = []
    for b in B:
        idx = sl.bisect_right(b)
        if idx < len(sl):
            res.append(sl.pop(idx))
        else:
            res.append(sl.pop(0))
    # Re-assign to correct positions
    # Simpler: sort B with indices
    n = len(B)
    ans = [0] * n
    sorted_A = sorted(nums)
    order = sorted(range(n), key=lambda i: B[i])
    lo, hi = 0, n - 1
    for a in sorted_A:
        if a > B[order[lo]]:
            ans[order[lo]] = a; lo += 1
        else:
            ans[order[hi]] = a; hi -= 1
    return ans

Complexity

Time: O(n log n)
Space: O(n)