Advantage Shuffle

LeetCode Q 870 - Advantage Shuffle

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.

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]

Note:

• 1 <= A.length = B.length <= 10000
• 0 <= A[i] <= 10^9
• 0 <= B[i] <= 10^9

Solution

We maximize its advantage greedily.
For a number in array B, among the larger numbers in array A we choose the smallest one. If we cannot find a larger number in A, we use the smallest number in A.

Solution 1: Use Heap

Code:

public int[] advantageCount(int[] A, int[] B) {
	
	Arrays.sort(A);

	PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[1]-a[1]));

	for (int i = 0; i < B.length; i++)
		pq.offer(new int[]{i, B[i]});

	int[] res = new int[A.length];
	int left = 0; right = A.length - 1;

	while (!pq.isEmpty()) {
		int[] curr = pq.poll();
		if (A[right] > curr[1])
			res[curr[0]] = A[right--];
		else
			res[curr[0]] = A[left++];
	}
	
	return res;
}

Solution 2: Use TreeMap

Code:

public int[] advantageCount(int[] A, int[] B) {
	
	TreeMap<Integer, Integer> map = new TreeMap<>();

	for (int a : A)
		map.put(a, map.getOrDefault(a, 0) + 1);

	int[] res = new int[A.length];

	for (int i = 0; i < B.length; i++) {
		Integer number = map.higherKey(B[i]);
		
		if (number == null)
			number = map.firstKey();
		
		map.put(x, map.get(x)-1);
		
		if (map.get(x) == 0) map.remove(x);
		
		res[i] = x;
	}

	return res;
}

TreeMap in Java
TreeMap is sorted map, built based on Red-Black tree. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at the map creation time. It is not thread safe. It provides many useful method, such as:

• ceilingKey(K key): Returns the least key greater than or equal to the given key, or null if there is no such key.
• ceilingEntry(K key): Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
• floorKey(K key): Returns the greatest key less than or equal to the given key, or null if there is no such key.
• floorEntry(K key): Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
• firstKey(): Returns the first (lowest) key currently in this map.
• lastKey(): Returns the last (highest) key currently in this map.
• higherKey(K key): Returns the least key strictly greater than the given key, or null if there is no such key.
• lowerKey(K key): Returns the greatest key strictly less than the given key, or null if there is no such key.