Solution: Advantage Shuffle
Tags: algorithms, javascript, java, python
Published: 2021-03-24 11:30:54

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/advantage-shuffle/discuss/1125217).*

---

#### [Leetcode Problem #870 (*Medium*): Advantage Shuffle](https://leetcode.com/problems/advantage-shuffle/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given two arrays `A` and `B` of equal size, the *advantage of `A` with respect to `B`* is the number of indices `i` for which `A[i] > B[i]`.
>
Return **any** permutation of `A` that maximizes its advantage with respect to `B`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|A = [2,7,11,15], B = [1,10,4,11]
Output:|[2,11,7,15]
>
Example 2:||
|---:|---|
Input:|A = [12,24,8,32], B = [13,25,32,11]
Output:|[24,32,8,12]

---

#### ***Constraints:***
>
 - `1 <= A.length = B.length <= 10000`
 - `0 <= A[i] <= 10^9`
 - `0 <= B[i] <= 10^9`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The general principle here is easy to understand: for each value in **B**, we ideally want to pick a number from **A** that is *just* higher to match up against it. The naive way to do this would require sorting **A**, then iterating through it until we find the ideal number, then removing that number from **A** and moving it to the answer array (**ans**) at a **time complexity** of **O(n^2)**.

We could employ a **binary search** instead of a straight iteration, which would drop the overall time complexity to **O(n * log n)**, matching the sort time complexity. The issue that remains, however, is that getting rid of elements of **A** can be time-consuming. (*Note: This method actually works well in Python; see the code below.*)

Instead, if we had a sorted **B** as well, we could just match up the values very easily in descending order. If the largest remaining value of **A** is larger than the largest remaining value of **B**, then use it, otherwise, use the smallest remaining value of **A**, which is the least useful.

Since we need to return our answer matched up agains the original order of **B**, however, we can't just sort **B**. We can, however, create an **index order lookup array** and sort it in reference to the values in **B**, then use it as a bridge between the sorted **A** and unsorted **B**.

Once we've finished iterating, we can **return ans**.

---

#### ***Implementation:***

Javascript as usual should take advantage of the faster typed arrays here.

As noted above, Python has a very short, competitively performant version using **bisect** and without needing to sort **B**.

Java will have to use a basic sort on **A**, as it's a primitive array, but we can make **ord** an Integer array so that we can use a **lambda** sort. That means we'll have to swap **i** and **j**.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var advantageCount = function(A, B) {
    let ord = Uint16Array.from({length:B.length}, (_,i) => i), 
        ans = new Uint32Array(B.length),
        i = 0, j = B.length - 1
    ord.sort((a,b) => B[b] - B[a])
    A.sort((a,b) => b - a)
    for (let ix of ord)
        ans[ix] = A[i] > B[ix] ? A[i++] : A[j--]
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        order = [i for i in range(len(B))]
        ans = [0 for _ in range(len(A))]
        order.sort(key=lambda x: -B[x])
        A.sort()
        for ix in order:
            ans[ix] = A.pop() if A[-1] > B[ix] else A.pop(0)
        return ans
```

---

#### ***Python Code w/ Binary Search:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        ans, A = [], sorted(A)
        for num in B:
            val = bisect_right(A, num)
            ans.append(A.pop(0) if val == len(A) else A.pop(val))
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        Integer[] ord = new Integer[B.length];
        int[] ans = new int[A.length];
        for (int i = 0; i < B.length; i++) ord[i] = i;
        Arrays.sort(ord, (a,b) -> Integer.compare(B[b], B[a]));
        Arrays.sort(A);
        int i = 0, j = B.length - 1;
        for (int ix : ord)
            ans[ix] = A[j] > B[ix] ? A[j--] : A[i++];
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> ord = vector<int>(B.size()), ans = vector<int>(A.size());
        for (int i = 0; i < B.size(); i++) ord[i] = i;
        sort(ord.begin(), ord.end(), [&](int a, int b) {return B[a] > B[b];});
        sort(A.begin(), A.end(), greater<>());
        int i = 0, j = B.size() - 1;
        for (int ix : ord)
            ans[ix] = A[i] > B[ix] ? A[i++] : A[j--];
        return ans;
    }
};
```