*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #870 (*Medium*): Advantage Shuffle

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given two arrays

`A`

and`B`

of equal size, theadvantage ofis the number of indices`A`

with respect to`B`

`i`

for which`A[i] > B[i]`

.Return

anypermutation of`A`

that maximizes its advantage with respect to`B`

.

####
*Examples:*

*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:*

*Constraints:*

`1 <= A.length = B.length <= 10000`

`0 <= A[i] <= 10^9`

`0 <= B[i] <= 10^9`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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:*

*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:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code w/ Binary Search:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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;
}
};
```

## Top comments (0)