I would be very grateful if someone can help me out here:
Given two arrays `A` and `B` of equal length, 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`.
Length of `A` can be upto `10000`
Input: `A = [12,24,8,32], B = [13,25,32,11]`
Output: `[24,32,8,12]`
I want to learn how to do problems like this so I am trying to go step-by-step with the Greedy method.
1Q) Find the greedy strategy
1A) I am struggling very deeply here, I am unable to find a greedy strategy that might work. Can anyone give some idea and motivation here?
A good starting point is to write a brute force algorithm to permute your array A and compute the max advantage. Once you have tried enough tests, you might be able to observe a pattern from there.
In this case it might be hard to do this because most of the test cases have a lot of optimal permutations.
Firstly, you should order A and B in descending order. Keep two pointers relative to A such that L starts off at the biggest element of A and R at the lowest element of A. After that, iterate over B. If A[L] > B[i], you should pair up these elements in the final permutation. Otherwise, pair up A[R] and B[i]. Don't forget to add 1 to L or subtract 1 from R after each step, depending on which of the elements of A you decided to use.
This will always generate the optimal answer because if the biggest element of A is bigger than the biggest of B, it makes sense to pair these such elements up. However, if no element of A is bigger than the biggest element of B, you should just use your lowest element, so that you won't "waste" your bigger elements.
Thanks!
Can you explain this part: "However, if no element of A is bigger than the biggest element of B, you should just use your lowest element, so that you won't "waste" your bigger elements." ?
I don't understand how you came up with this or why its true.
Thanks
If the biggest element from B (I'll call it K from now on) is larger or equal to any of the elements in A, no matter what element from A you pair K up with it won't increment to your final answer. Therefore, you should pair K up with the smallest element remaining from A so that you can complete the rest of the array in a more efficient manner.