Algorithm
Problem Name: 870. Advantage Shuffle
Problem Link: https://leetcode.com/problems/advantage-shuffle/
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 <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] advantageCount(int[] A, int[] B) {
TreeMap map = new TreeMap<>();
for (int num : A) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int[] result = new int[A.length];
Arrays.fill(result, Integer.MIN_VALUE);
List < Integer> indexesNotPopulated = new ArrayList<>();
for (int i = 0; i < B.length; i++) {
Integer upper = map.higherKey(B[i]);
if (upper != null) {
result[i] = upper;
map.put(upper, map.get(upper) - 1);
if (map.get(upper) == 0) {
map.remove(upper);
}
} else {
indexesNotPopulated.add(i);
}
}
Iterator < Integer> iterator = indexesNotPopulated.iterator();
for (Integer key : map.keySet()) {
int value = map.get(key);
while (value-- > 0) {
result[iterator.next()] = key;
}
}
return result;
}
}
Input
nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output
[2,11,7,15]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
function advantageCount(aArr, B) {
const A = aArr.sort((a, b) => a - b)
const n = A.length
const res = []
let pq = []
for(let i = 0; i < n; i++) {
pq.push([B[i], i])
}
pq.sort((a, b) => b[0] - a[0])
let lo = 0
let hi = n - 1
while(pq.length > 0) {
let cur = pq.shift()
let idx = cur[1]
let val = cur[0]
if (A[hi] > val) {
res[idx] = A[hi--]
} else {
res[idx] = A[lo++]
}
}
return res
}
Input
nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output
[2,11,7,15]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
A.sort(reverse = True)
non = []
res = [-1] * len(A)
for b, i in sorted([(b, i) for i, b in enumerate(B)]):
while A and A[-1] <= b:
non.append(A.pop())
if A:
res[i] = A.pop()
else:
break
for i in range(len(res)):
if res[i] == -1:
res[i] = non.pop()
return res
Input
nums1 = [12,24,8,32], nums2 = [13,25,32,11]
Output
[24,32,8,12]