Permuting Two Arrays

Published on August 20, 2021
Last updated August 20, 2021

There are two n-element arrays of integers, A and B. Permute them into some a and b such that the relation a[i] + b[i] >= k holds for all i where 0 <= i < n.

Sample Input

STDIN       Function
-----       --------
2           q = 2
3 10        A[] and B[] size n = 3, k = 10
2 1 3       A = [2, 1, 3]
7 8 9       B = [7, 8, 9]
4 5         A[] and B[] size n = 4, k = 5
1 2 2 1     A = [1, 2, 2, 1]
3 3 3 4     B = [3, 3, 3, 4]

Sample Output

YES
NO

Solution in java

import java.util.Arrays;
import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num_of_cases = sc.nextInt();
        while (num_of_cases > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            boolean result = true;
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) {
                b[i] = sc.nextInt();
            }
            Arrays.sort(a);
            Arrays.sort(b);
            for (int i = 0; i < n; i++) {
                if (a[i] + b[n - i - 1] < k) {
                    result = false;
                    break;
                }
            }
            System.out.println(result ? "YES" : "NO");
            num_of_cases--;
        }
        sc.close();
    }
}


Tags :