Code Implementation

from typing import List

class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        A_sorted = sorted(A)
        # Store original indices of B
        B_with_indices = sorted([(b, i) for i, b in enumerate(B)])
        res = [0] * len(A)
        left, right = 0, len(A) - 1
        for a in A_sorted:
            # If a can beat the smallest remaining in B
            if a > B_with_indices[left][0]:
                res[B_with_indices[left][1]] = a
                left += 1
            else:
                # Assign a to the largest remaining in B
                res[B_with_indices[right][1]] = a
                right -= 1
        return res
      

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> A_sorted = A;
        sort(A_sorted.begin(), A_sorted.end());
        int n = A.size();
        vector<pair<int, int>> B_with_indices;
        for (int i = 0; i < n; ++i) {
            B_with_indices.push_back({B[i], i});
        }
        sort(B_with_indices.begin(), B_with_indices.end());
        vector<int> res(n);
        int left = 0, right = n - 1;
        for (int a : A_sorted) {
            if (a > B_with_indices[left].first) {
                res[B_with_indices[left].second] = a;
                ++left;
            } else {
                res[B_with_indices[right].second] = a;
                --right;
            }
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        int n = A.length;
        int[] res = new int[n];
        Arrays.sort(A);
        int[][] B_with_indices = new int[n][2];
        for (int i = 0; i < n; i++) {
            B_with_indices[i][0] = B[i];
            B_with_indices[i][1] = i;
        }
        Arrays.sort(B_with_indices, Comparator.comparingInt(a -> a[0]));
        int left = 0, right = n - 1;
        for (int a : A) {
            if (a > B_with_indices[left][0]) {
                res[B_with_indices[left][1]] = a;
                left++;
            } else {
                res[B_with_indices[right][1]] = a;
                right--;
            }
        }
        return res;
    }
}
      

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */
var advantageCount = function(A, B) {
    let A_sorted = [...A].sort((a, b) => a - b);
    let n = A.length;
    let B_with_indices = B.map((b, i) => [b, i]);
    B_with_indices.sort((a, b) => a[0] - b[0]);
    let res = new Array(n);
    let left = 0, right = n - 1;
    for (let a of A_sorted) {
        if (a > B_with_indices[left][0]) {
            res[B_with_indices[left][1]] = a;
            left++;
        } else {
            res[B_with_indices[right][1]] = a;
            right--;
        }
    }
    return res;
};
      

Problem Description

Given two arrays of integers, A and B, both of the same length, you are asked to rearrange A so as to maximize the number of positions where A[i] > B[i].
For each index i, you may use each element from A exactly once and must assign each to a position in the result array. The final arrangement should maximize the number of indices where A[i] is strictly greater than B[i].
You are guaranteed that at least one valid solution exists. Elements from A cannot be reused, and the output must be a permutation of A.

Thought Process

At first glance, one might think to try all possible permutations of A and count the number of times A[i] > B[i] for each arrangement, keeping the best. However, this brute-force idea is not practical for large arrays due to the factorial number of permutations.
Instead, we can look for a more efficient strategy. Since we want to maximize the number of positions where A[i] beats B[i], it makes sense to "save" our biggest numbers in A for the biggest numbers in B that we can't beat, and use the smallest numbers in A to beat the smallest numbers in B when possible.
This suggests a greedy approach: always try to use the smallest number from A that can beat the smallest remaining number from B. If we can't beat any, sacrifice our smallest number from A against the largest remaining in B.

Solution Approach

• Step 1: Sort A in ascending order. This allows us to efficiently pick the smallest or largest available value.
• Step 2: Pair each value in B with its index and sort these pairs by the values in B. This way, we know which values we are trying to beat and can assign to the correct index later.
• Step 3: Use two pointers: one at the start (left) and one at the end (right) of the sorted B array.
• Step 4: For each value a in the sorted A:
  • If a is greater than B[left], assign a to beat B[left] and move left forward.
  • Otherwise, assign a to B[right] (where it can't win anyway) and move right backward.
• Step 5: Place each assigned value from A at the correct index in the result array according to the original index in B.
• This greedy method ensures that every time we can win, we do so with the smallest possible A, and when we can't win, we "sacrifice" the smallest A on the hardest-to-beat B.

Example Walkthrough

Example:
A = [2,7,11,15]
B = [1,10,4,11]

1. Sort A: [2, 7, 11, 15]
2. Pair and sort B with indices: [(1,0), (4,2), (10,1), (11,3)]
3. Set left = 0 (points to 1), right = 3 (points to 11)
4. Iterate through A:
   • 2 > 1: assign 2 to index 0, left++ (left=1)
   • 7 > 4: assign 7 to index 2, left++ (left=2)
   • 11 > 10: assign 11 to index 1, left++ (left=3)
   • 15 > 11: assign 15 to index 3, left++ (left=4)
5. Result: [2,11,7,15]
6. Count of A[i] > B[i]: 4 (all positions)

This process ensures we maximize wins and always use the smallest possible value for each win.

Time and Space Complexity

• Brute-force Approach:
  • Would involve checking all permutations of A (O(n!)), which is infeasible for large n.
• Optimized Approach (the one above):
  • Sorting A: O(n log n)
  • Sorting B with indices: O(n log n)
  • One pass through A: O(n)
  • Total Time Complexity: O(n log n)
  • Space Complexity: O(n) for the result and auxiliary arrays

The optimized approach is much faster and more memory-efficient than brute-force.

Summary

The Advantage Shuffle problem is elegantly solved with a greedy strategy: always use the smallest available number to win when possible, and otherwise "sacrifice" it where it can't win. By sorting both arrays and using two pointers, we efficiently maximize our wins while ensuring every element is used once. This approach avoids brute-force and leverages sorting and careful assignment to achieve the optimal result in O(n log n) time.