Here is a detailed explanation of why sorting solves this problem:

We can sort array A ascending and sort array B descending, and then because they are sorted we know that we are matching the highest possible from B with the lowest possible from A each time and if 1 of those fails then we know it is not possible. The reason we know this is true is because they are inversely sorted, so we have already made the optimal decision at each stage in terms of the amount of absolute difference we have 'wasted/extra' thus leaving us with the tightest bounding number to k for each index. Because it is the tightest bound number, there is no other permutation that will pass if 1 comparison fails.

Optimizations to think about:

• If you use a StringBuilder to build your answers to queries and then only make a single System.out call it will be much faster because I/O is slow
• If we want to sort a int array in descending order using the built in libraries, we have to change it to an Integer[] which takes up 16 bytes per element compared to 4. So instead what we can do is sort the int[] ascending and just traverse it in reverse when comparing to view the elements in descending order

Java Solution Here is my solution in Java that passes all cases in O(n log(n)) time with O(n) space.

For more solutions like this check out the HackerRank Github repo here