Leetcode 870. Advantage Shuffle
Problem Explanation
Given two arrays of equal size, the problem requires us to maximize the advantage of an array A
over B
. The advantage of A
over B
is defined as the number of indices i
for which A[i] > B[i]
.
The task is to return any permutation of A
that gives the maximum advantage.
Let's consider an example to illustrate how this works:
If we have A=[2,7,11,15]
and B=[1,10,4,11]
, the best permutation of A
to maximize the advantage over B
is [2,11,7,15]
.
Here's why this permutation works:
- For
i=0
,A[0]=2
andB[0]=1
; sinceA[0] > B[0]
,A
has an advantage at this index. - For
i=1
,A[1]=11
andB[1]=10
;A[1]
is also greater, givingA
an advantage at this index as well. - For
i=2
,A[2]=7
andB[2]=4
;A
continues to have an advantage. - But for
i=3
,A[3]=15
andB[3]=11
; However,A[3]
is not greater thanB[3]
, so it does not give an advantage toA
at this index.
So A
has an advantage at 3 out of 4 indices, which is the maximum possible for this particular pair of arrays.
Approach
The problem can be solved using a multiset
and greedy
approach.
Here is how the solution works:
-
Initialize a
multiset
with the elements ofA
. Amultiset
is a data structure that maintains a sorted list of elements and allows duplicate entries. The elements in amultiset
are always in non-descending order. -
Run a loop on
B
. For each element inB
, find the element in themultiset
that is just above the current element inB
. If no such element is found (which means all the elements in themultiset
are less than or equal to the current element inB
), take the smallest element in themultiset
. -
As we pick the elements from the
multiset
, remove them from themultiset
and place them at the corresponding position inA
. -
Return the updated
A
as the result.
Python Solution
1 2python 3from sortedcontainers import SortedSet 4 5class Solution: 6 def advantageCount(self, A: List[int], B: List[int]) -> List[int]: 7 sortedA = SortedSet(A) 8 res = [] 9 for b in B: 10 # If the smallest in A is bigger than b 11 if sortedA[0] > b: 12 a = sortedA.pop(0) 13 # Else remove the smallest that is just bigger than b 14 else: 15 a = sortedA.pop(sortedA.bisect_right(b)) 16 res.append(a) 17 return res
Java Solution
1 2java 3class Solution { 4 public int[] advantageCount(int[] A, int[] B) { 5 6 int[] sortedA = A.clone(); 7 int[] sortedB = B.clone(); 8 9 Arrays.sort(sortedA); 10 Arrays.sort(sortedB); 11 12 Map<Integer, Deque<Integer>> assigned = new HashMap(); 13 for (int b: B) 14 assigned.put(b, new LinkedList()); 15 16 Deque<Integer> remaining = new LinkedList(); 17 18 int j = 0; 19 for (int a: sortedA) { 20 if (a > sortedB[j]) { 21 assigned.get(sortedB[j++]).add(a); 22 } 23 else { 24 remaining.add(a); 25 } 26 } 27 28 for (int i = 0; i < B.length; ++i) { 29 if (assigned.get(B[i]).size() > 0) 30 A[i] = assigned.get(B[i]).pop(); 31 else 32 A[i] = remaining.pop(); 33 } 34 return A; 35 } 36}
JavaScript Solution
1
2javascript
3
4var advantageCount = function(A, B) {
5 let sortedA = A.sort((a,b) => a-b);
6 let sortedB = B.sort((a,b) => a-b).map(b => { return {val:b, used:false}});
7 let map = {};
8 let remain = [];
9 let j = 0;
10
11 for (let num of sortedA) {
12 if (num > sortedB[j].val) {
13 if (map[sortedB[j].val]) {
14 map[sortedB[j].val].push(num);
15 } else {
16 map[sortedB[j].val] = [num];
17 }
18 j++;
19 } else {
20 remain.push(num);
21 }
22 }
23
24 return B.map(b => {
25 if (map[b] && map[b].length > 0) {
26 return map[b].pop();
27 } else {
28 return remain.pop();
29 }
30 })
31};
32
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<int> advantageCount(vector<int>& A, vector<int>& B) {
6 multiset<int> s(A.begin(), A.end());
7 for (int i=0; i<B.size(); i++) {
8 auto p = *s.rbegin() <= B[i] ? s.begin() : s.upper_bound(B[i]);
9 A[i] = *p;
10 s.erase(p);
11 }
12 return A;
13 }
14};
C# Solution
1 2C# 3public class Solution { 4 public int[] AdvantageCount(int[] A, int[] B) { 5 int n = A.Length; 6 var pairs = new Tuple<int, int>[n]; 7 for (int i = 0; i < n; i++) 8 pairs[i] = Tuple.Create(B[i], i); 9 Array.Sort(pairs, (a, b) => a.Item1 - b.Item1); 10 Array.Sort(A); 11 var res = new int[n]; 12 var j = 0; 13 for (int i = 0; i < n; i++) { 14 if (j < n && A[j] <= pairs[i].Item1) { 15 res[pairs[i].Item2] = A[j++]; 16 } else { 17 res[pairs[i].Item2] = A[--n]; 18 } 19 } 20 return res; 21 } 22}
In each of the above solutions, we start by sorting both arrays A
and B
. In the Python and C++ solutions, we make use of a SortedSet
and multiset
data structure respectively. In the Java solution, we use a HashMap
and Deque
to keep track of elements in B
that are smaller than any element in A
. The JavaScript solution uses a map to track elements in B
greater than any elements in A
and stores the remaining items in an array named remain
.
Time Complexity
The time complexity of the above solutions is primarily dictated by the sort operation, which is O(n log n) for all inputs. n
is the number of elements in the input arrays.
Apart from the sorting, the remaining operations including finding the just greater element and relocating the smallest element take linear time, hence won't affect the overall time complexity.
Space Complexity
The space complexity of the solutions is O(n), where n
is the number of elements in A
. This is because, in the worst-case scenario, we have to store all the elements of A
in an additional data structure.
These solutions hence provide an efficient way to maximize the advantage of one array over another.
Conclusion
The problem of maximizing the advantage of one array over another can be solved using greedy algorithms. We discussed solutions coded in Python, Java, JavaScript, C++, and C#. They all follow a similar strategy โ sorting the arrays and then efficiently finding the best element of A
to use for each element of B
. This ensures that we get the maximum possible advantage of A
over B
in the resulting permutation.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.