870. Advantage Shuffle #

Problem #

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

Main Idea #

Given two arrays A and B of equal size, the advantage of A with respect to B can be described by the number of indices i for which A[i] > B[i]. Return any permutation of A that maximizes its advantage with respect to B.

Solution Approach #

This problem is solved using a greedy algorithm. If the smallest card a in A can beat the smallest card b in B, then pair them. Otherwise, a will not help our score because it cannot beat any card. This is the greedy strategy: each match uses the weakest card in hand to pair with the smallest card b in B, which makes the remaining cards in A strictly larger and will ultimately lead to a higher score.
In the code implementation, sort array A, and sort array B by index. Since the final output is the advantage result with respect to B, the permutation of A must be arranged while keeping B’s indices unchanged. After sorting, choose the order of the cards in A according to the greedy strategy.

Code #

package leetcode

import "sort"

func advantageCount1(A []int, B []int) []int {
	n := len(A)
	sort.Ints(A)
	sortedB := make([]int, n)
	for i := range sortedB {
		sortedB[i] = i
	}
	sort.Slice(sortedB, func(i, j int) bool {
		return B[sortedB[i]] < B[sortedB[j]]
	})
	useless, i, res := make([]int, 0), 0, make([]int, n)
	for _, index := range sortedB {
		b := B[index]
		for i < n && A[i] <= b {
			useless = append(useless, A[i])
			i++
		}
		if i < n {
			res[index] = A[i]
			i++
		} else {
			res[index] = useless[0]
			useless = useless[1:]
		}
	}
	return res
}