Permuting Two Arrays
Hello World!
Let’s get going with the problem Permuting Two Arrays on HackerRank. You may click on the title to read the problem statement. So let’s start…
We have been given two arrays A and B of equal length. We are asked to find if we can permute the given arrays to A’ and B’ such that A’[i] + B’[i] ≥ k for all 0 ≤ i < n. Here, we will sort A in ascending order and B in descending order. And now we will check for the given constraint for every i.
This works because we take highest possible element from A and match it with lowest possible element from B. This works because by inversely sorting the arrays, we’ve already made an optimal decision to minimize the absolute difference wasted. Thus, we have tightest bounding number to k for each index.
So if even one index fails to satisfy the given condition, we terminate the loop and print “NO”. If all the indexes satisfy the give condition, then we print “YES”.
Open for suggestions. The code for this problem in Python3 can be found here.
Happy coding…