We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Permuting Two Arrays
You are viewing a single comment's thread. Return to all comments →
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:
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