# Advantage Shuffle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/advantage-shuffle)
Canonical: https://scaleengineer.com/dsa/problems/advantage-shuffle
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Point72](https://scaleengineer.com/companies/point72)
---
## Problem
You are given two integer arrays `nums1` and `nums2` both of the same length. The **advantage** of `nums1` with respect to `nums2` is the number of indices `i` for which `nums1[i] > nums2[i]`.

Return _any permutation of_ `nums1` _that maximizes its **advantage** with respect to_ `nums2`.

**Example 1:**

**Input:** nums1 = [2,7,11,15], nums2 = [1,10,4,11]
**Output:** [2,11,7,15]

**Example 2:**

**Input:** nums1 = [12,24,8,32], nums2 = [13,25,32,11]
**Output:** [24,32,8,12]

**Constraints:**

* `1 <= nums1.length <= 105`
* `nums2.length == nums1.length`
* `0 <= nums1[i], nums2[i] <= 109`

# Approaches
## Brute Force by Generating All Permutations
The most straightforward but computationally expensive approach is to try every possible arrangement of `nums1`. We can generate all permutations of `nums1` and, for each one, calculate the advantage score against `nums2`. We then return the permutation that gives the maximum score.
**Time:** O(n! * n) - There are `n!` permutations of `nums1`. For each permutation, we take `O(n)` time to calculate its advantage. This is prohibitively slow. · **Space:** O(n) - The space is dominated by the recursion stack depth for permutation generation and storing the best permutation found, both of which are proportional to `n`.
**Pros:** Guaranteed to find the optimal solution.; Conceptually simple to understand.
**Cons:** Extremely inefficient due to the factorial time complexity.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.; Impractical for the given constraints (`n` up to 10^5).
### Explanation
This method explores the entire solution space by generating all `n!` permutations of the `nums1` array. For each generated permutation, we iterate from `i = 0` to `n-1` and count how many times `permutation[i] > nums2[i]`. We maintain a variable to store the maximum advantage found so far and the corresponding permutation. While this guarantees finding an optimal solution, its factorial time complexity makes it infeasible for anything but very small arrays.

```java
// NOTE: This is a conceptual implementation and will time out.
// A proper permutation generator for arrays with duplicates would be more complex.
class Solution {
    int maxAdvantage = -1;
    int[] bestPermutation;

    public int[] advantageCount(int[] nums1, int[] nums2) {
        bestPermutation = new int[nums1.length];
        permute(nums1, 0, nums2);
        return bestPermutation;
    }

    private void permute(int[] nums, int start, int[] nums2) {
        if (start >= nums.length) {
            int currentAdvantage = calculateAdvantage(nums, nums2);
            if (currentAdvantage > maxAdvantage) {
                maxAdvantage = currentAdvantage;
                bestPermutation = nums.clone();
            }
            return;
        }
        java.util.Set<Integer> used = new java.util.HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (used.add(nums[i])) { // Handle duplicates
                swap(nums, start, i);
                permute(nums, start + 1, nums2);
                swap(nums, start, i); // backtrack
            }
        }
    }
    
    private int calculateAdvantage(int[] p, int[] nums2) {
        int count = 0;
        for (int i = 0; i < p.length; i++) {
            if (p[i] > nums2[i]) {
                count++;
            }
        }
        return count;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- Generate every possible permutation of `nums1`.
- For each permutation, calculate its "advantage" by comparing it element-wise with `nums2`.
- Keep track of the permutation that yields the highest advantage score.
- After checking all permutations, return the best one found.

## Greedy Approach with Repeated Searching
A more refined approach is to use a greedy strategy. For each element in `nums2`, we try to find the best possible number from `nums1` to assign to it. The "best" number is the smallest one that is still larger than the `nums2` element, as this saves our larger numbers for tougher opponents. If we can't beat the `nums2` element, we use our smallest available number from `nums1` as a sacrifice.
**Time:** O(n^2) - Sorting `nums1` takes `O(n log n)`. The main loop runs `n` times. Inside the loop, binary search takes `O(log n)`, but removing an element from an `ArrayList` takes `O(n)` time in the worst case. This makes the total complexity `O(n * n) = O(n^2)`. · **Space:** O(n) - We need a list to store the elements of `nums1`, which takes `O(n)` space. The result array also takes `O(n)` space.
**Pros:** Implements a correct greedy logic.; Much more efficient than the brute-force approach.
**Cons:** The time complexity is `O(n^2)` due to the removal of elements from the list inside the loop.; This will likely result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This greedy approach improves upon brute force by making a locally optimal choice at each step. We first sort `nums1` to easily find the smallest or smallest-greater elements. We then iterate through `nums2` in its original order. For each `nums2[i]`, we need to pick a number from the available numbers in `nums1`. The best strategy is to pick the smallest number that can beat `nums2[i]`. This can be found efficiently using binary search on the sorted list of available `nums1` numbers. If no number can beat `nums2[i]`, we must lose. To save our better cards for other positions, we sacrifice our weakest available card (the smallest number overall). The main performance bottleneck is removing an element from the list (an `ArrayList` in Java), which takes linear time in the size of the list, leading to an overall quadratic time complexity.

```java
import java.util.*;

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        List<Integer> sortedNums1 = new ArrayList<>();
        for (int num : nums1) {
            sortedNums1.add(num);
        }
        Collections.sort(sortedNums1);

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int target = nums2[i];
            
            // Binary search to find the smallest element > target
            int low = 0, high = sortedNums1.size() - 1;
            int bestChoiceIdx = -1;
            while(low <= high){
                int mid = low + (high - low) / 2;
                if(sortedNums1.get(mid) > target){
                    bestChoiceIdx = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }

            if (bestChoiceIdx != -1) {
                // If a winning number is found, use the smallest one
                result[i] = sortedNums1.get(bestChoiceIdx);
                sortedNums1.remove(bestChoiceIdx); // O(n) operation
            } else {
                // Otherwise, use the smallest available number as a sacrifice
                result[i] = sortedNums1.get(0);
                sortedNums1.remove(0); // O(n) operation
            }
        }
        return result;
    }
}
```
### Algorithm
- Sort `nums1` in ascending order and place its elements into a list for efficient removal.
- Initialize an empty result array `ans`.
- Iterate through `nums2` from `i = 0` to `n-1`.
- For each `nums2[i]`, search for the smallest element in the list of available `nums1` numbers that is strictly greater than `nums2[i]`.
- If such an element is found, place it in `ans[i]` and remove it from the list.
- If no such element is found, it's impossible to gain an advantage at index `i`. Place the smallest available element from `nums1` (a "throwaway" number) in `ans[i]` and remove it from the list.
- Return the `ans` array.

## Optimal Greedy Approach with Two Pointers
This is an optimal greedy approach that uses sorting and a two-pointer technique. The core idea is to match our strongest available number from `nums1` against the strongest opponent in `nums2`. If we can win, we take the advantage. If we can't, we know our strongest number is not strong enough, so we sacrifice our weakest number against this unbeatable opponent, saving our strongest number for a weaker opponent it might be able to beat.
**Time:** O(n log n) - The dominant operations are sorting `nums1` and `sortedNums2`, both of which take `O(n log n)`. The final two-pointer traversal takes `O(n)` time. · **Space:** O(n) - We need `O(n)` space for the `sortedNums2` structure that stores values and original indices. The result array also requires `O(n)` space.
**Pros:** Highly efficient with `O(n log n)` time complexity.; Correctly implements the optimal greedy strategy.; Passes all constraints.
**Cons:** Requires extra space (`O(n)`) to store the sorted version of `nums2` along with its original indices.
### Explanation
To implement this efficiently, we sort `nums1` in ascending order. Since we need to place the results back in an array corresponding to the original `nums2`, we can't sort `nums2` directly. Instead, we create a structure (like a 2D array or a custom class) to hold both the value and original index of each element in `nums2`, and then sort this structure. 

We then use two pointers, `low` and `high`, on the sorted `nums1` array, pointing to the weakest and strongest available numbers, respectively. We iterate through our sorted `nums2` structure from the strongest opponent downwards. For each opponent, we check if our strongest card (`nums1[high]`) can win. If it can, we use it and move to our next strongest card (`high--`). If it cannot, we must lose this matchup. To maximize our chances elsewhere, we use our weakest, "throwaway" card (`nums1[low]`) and move to our next weakest card (`low++`). The result is placed in the final answer array at the opponent's original index.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        
        // Sort nums1 in ascending order
        Arrays.sort(nums1);
        
        // Create a 2D array to store nums2 elements with their original indices
        int[][] sortedNums2 = new int[n][2];
        for (int i = 0; i < n; i++) {
            sortedNums2[i][0] = nums2[i];
            sortedNums2[i][1] = i;
        }
        
        // Sort sortedNums2 based on values in ascending order
        Arrays.sort(sortedNums2, Comparator.comparingInt(a -> a[0]));
        
        int[] result = new int[n];
        
        // Pointers for nums1
        int low = 0;
        int high = n - 1;
        
        // Iterate through sortedNums2 from strongest opponent to weakest
        for (int i = n - 1; i >= 0; i--) {
            int originalIndex = sortedNums2[i][1];
            int opponentValue = sortedNums2[i][0];
            
            // If our strongest card can beat their strongest opponent, use it.
            if (nums1[high] > opponentValue) {
                result[originalIndex] = nums1[high];
                high--;
            } else {
                // Otherwise, sacrifice our weakest card.
                result[originalIndex] = nums1[low];
                low++;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Sort `nums1` in ascending order.
- Create a data structure (e.g., a 2D array) to store pairs of `(value, original_index)` for `nums2`, and sort it by value in ascending order.
- Initialize an empty result array `ans` of size `n`.
- Use two pointers for the sorted `nums1`: `low` starting at `0` and `high` starting at `n-1`.
- Iterate through the sorted `nums2` from the largest element to the smallest.
- In each step, consider the strongest remaining opponent from `nums2`.
- Compare it with our strongest available card from `nums1` (at `nums1[high]`).
- If `nums1[high]` can beat the opponent, assign `ans[original_index] = nums1[high]` and decrement `high`.
- If `nums1[high]` cannot beat the opponent, we must sacrifice a card. To save our stronger cards, we sacrifice our weakest card, `nums1[low]`. Assign `ans[original_index] = nums1[low]` and increment `low`.
- After the loop, return the `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] advantageCount(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[][] t = new int[n][2];
    for (int i = 0; i < n; ++i) {
      t[i] = new int[]{nums2[i], i};
    }
    Arrays.sort(t, (a, b)->a[0] - b[0]);
    Arrays.sort(nums1);
    int[] ans = new int[n];
    int i = 0, j = n - 1;
    for (int v : nums1) {
      if (v <= t[i][0]) {
        ans[t[j--][1]] = v;
      } else {
        ans[t[i++][1]] = v;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2) {
    int n = nums1.size();
    vector<pair<int, int>> t;
    for (int i = 0; i < n; ++i)
      t.push_back({nums2[i], i});
    sort(t.begin(), t.end());
    sort(nums1.begin(), nums1.end());
    int i = 0, j = n - 1;
    vector<int> ans(n);
    for (int v : nums1) {
      if (v <= t[i].first)
        ans[t[j--].second] = v;
      else
        ans[t[i++].second] = v;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1 . sort() t = sorted((v, i) for i, v in enumerate(nums2)) n = len(nums2) ans = [0] * n i, j = 0, n - 1 for v in nums1: if v <= t[i][0]: ans[t[j][1]] = v j -= 1 else: ans[t[i][1]] = v i += 1 return ans

```