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.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Permuting Two Arrays
  5. Discussions

Permuting Two Arrays

  • renolu
     + 1 comment

    Here is a simple approaching in Java: 1. sort both array1 and array2, one in ascending and one in descending order 2. add biggest to smallest, 2nd biggest to 2nd smallest and so on... If any of these pairs's sum are smaller than k, return false. 3. After checking both arrays, if no pair's sum is smaller than k, return true

    import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        
        for(int i_t = 0; i_t<t;i_t++){
            int n=s.nextInt();
            Integer k=s.nextInt();
            Integer[] arr1 = new Integer[n];
            Integer[] arr2 = new Integer[n];
            for(int i=0;i<n;i++){
                arr1[i]=s.nextInt();                
            }
            for(int i=0;i<n;i++){
                arr2[i]=s.nextInt();                
            }
            
            if(isPermutable(arr1,arr2,k)){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
    
    
    static boolean isPermutable(Integer[] arr1, Integer[] arr2, Integer k){
        //sort in ascending order
        Arrays.sort(arr1);
        //sort in descending order
        Arrays.sort(arr2,Collections.reverseOrder());
        //matching largest with smaller, 2nd largest with 2nd smallest, and so on
        for(int i=0;i<arr1.length;i++){
            //if any of those pairs is less than k, return false
            if(arr1[i]+arr2[i]<k){
                return false;
            }
        }
        //after traversing the whole length, return true
        return true;
    }
}