- Practice
- Algorithms
- Greedy
- Permuting Two Arrays
- Discussions

# Permuting Two Arrays

# Permuting Two Arrays

ryanfehr18 + 1 comment **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**sarathy_v_krish1 + 0 comments C++ solution :

string twoArrays(int k, vector<int> A, vector<int> B) { sort(A.begin(), A.end()); sort(B.begin(), B.end(), greater<int>()); for (int i=0;i<A.size();i++) if (A[i]+B[i]<k) return "NO"; return "YES"; }

ray10mathew + 1 comment This was a ridiculously easy question. The arrays just needed to sorted in orders reverse of each other. Not worth 40 points...

chammika + 1 comment Very simple solution:

def twoArrays(k, A, B): A.sort() B.sort(reverse=True) if (any(a+b<k for a,b in zip(A,B))): return "NO" else: return "YES"

qayum_khan_usa + 0 comments Independently, here is

**1-codeline Python3**solution that represents the same idea.def twoArrays(k, A, B): return "YES" if all( sum(c)>=k for c in zip(sorted(A,reverse=True),sorted(B)) ) else "NO"

marinskiy + 0 comments Here is

**Python 3**solution from my HackerrankPractice repository:n = int(input()) for _ in range(n): __, k = map(int, input().split()) a = sorted(list(map(int, input().split()))) b = sorted(list(map(int, input().split())), reverse=True) if all([a[i] + b[i] >= k for i in range(len(a))]): print('YES') else: print('NO')

Feel free to ask if you have any questions :)

Sort 192 Discussions, By:

Please Login in order to post a comment