870. Advantage Shuffle

Description

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.

Constraints

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

2. 0 <= A[i] <= 10^9

3. 0 <= B[i] <= 10^9

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: A = [2, 7, 11, 15], B = [1, 10, 4, 11]

Output: [2, 11, 7, 15]

Example 2

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        int[] result = new int[A.length];
        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 slow = 0, fast = A.length-1;
        while(!pq.isEmpty()) {
            int[] b = pq.poll();
            result[b[0]] = b[1] >= A[fast]? A[slow++]: A[fast--];
        }
        
        return result;
    }
}

Follow up