Permute two arrays such that sum of every pair is greater or equal to K Easy 0 attempts
GeeksforGeeks ↗

Permute two arrays such that sum of every pair is greater or equal to K

Easy Sorting&Searching GeeksforGeeks

You're given two integer arrays A and B, each of size N, and a number K. Figure out whether the elements of A and B can each be rearranged (independently) so that, at every index i, A[i] + B[i] >= K.

Input Format
Implement canPermute(A, B, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
A = [2,1,3]
B = [7,8,9]
k = 10
Output
true

Example 2

Input
A = [1,2]
B = [1,2]
k = 5
Output
false
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i], B[i] <= 10^6
Test Cases (2)
Case 1
Args: [[2,1,3],[7,8,9],10] Expected: true
Case 2
Args: [[1,2],[1,2],5] Expected: false
Topics
Sorting&Searching

Sort + Greedy

Sort A ascending and B descending, check each pair.

javascript
function canPermute(A, B, k) {
  A.sort((a,b) => a-b); B.sort((a,b) => b-a);
  return A.every((a,i) => a + B[i] >= k);
}

Time: O(n log n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript