Permute Two Arrays such that Sum of Every Pair is Greater or Equal to K

We have given two arrays of equal size n and an integer k. The task is to permute both arrays such that sum of their corresponding element is greater than or equal to k i.e a[i] + b[i] >= k. The task is to print “Yes” if any such permutation exists, otherwise print “No”.

Example 1

Input:

a[] = {4, 2, 3, 1}

b[] = {5, 6, 7, 8}

k = 8

Output: Yes

Explanation: One possible permutation is a[] = {1, 2, 3, 4} and b[] = {8, 7, 6, 5}. With this permutation, the sum of corresponding elements is {1+8, 2+7, 3+6, 4+5} = {9, 9, 9, 9}, all of which are greater than or equal to k.

Example 2

Input:

a[] = {3, 5, 7}

b[] = {9, 10, 11}

k = 15

Output: Yes

Explanation: One possible permutation is a[] = {3, 5, 7} and b[] = {11, 10, 9}. With this permutation, the sum of corresponding elements is {3+11, 5+10, 7+9} = {14, 15, 16}, all of which are greater than or equal to k.

Approach

We first sort one array in ascending order and the other array in descending order. Then, we iterate through both arrays simultaneously and check if the sum of the corresponding elements satisfies the condition. If any pair violates the condition, we return "No"; otherwise, we return "Yes".

1. Sort array a in ascending order using Arrays.sort(a).
2. Sort array b in descending order using Arrays.sort(b, Collections.reverseOrder()).
3. Iterate over the arrays from index 0 to the length of the arrays.
4. Check if the sum of a[i] and b[n - 1 - i] (where n is the length of the arrays) is less than k.
5. If any pair violates this condition, return "No".
6. If all pairs satisfy the condition, return "Yes".

Complexity

• Time Complexity: O(n log n), where n is the size of the array.
• Space Complexity: O(1)

Code

import java.util.Arrays;

public class CanPermute {

    public static String canPermute(int[] a, int[] b, int k) {
        int n = a.length;
        Arrays.sort(a);
        Arrays.sort(b);

        // Check if a permutation exists such that a[i] + b[i] >= k for all i
        for (int i = 0; i < n; i++) {
            if (a[i] + b[n - 1 - i] < k) {
                return "No";
            }
        }
        return "Yes";
    }

    public static void main(String[] args) {
        int[] a1 = { 4, 2, 3, 1 };
        int[] b1 = { 5, 6, 7, 8 };
        int k1 = 8;

        System.out.println("Example 1 :" + canPermute(a1, b1, k1));

        int[] a2 = { 3, 5, 7 };
        int[] b2 = { 9, 10, 11 };
        int k2 = 5;

        System.out.println("Example 2 :" + canPermute(a2, b2, k2));
    }
}

Output

Example 1 :Yes
Example 2 :Yes