Determine if it is possible to choose K and M elements from array A and B respectively,such that every chosen element of K is less than every chosen element of M

Problem Statement

Given two arrays A & B of length N_a  and N_b respectively and two integer K and M,the task is to determine whether it is possible to select K elements from Array A and M elements from Array B such that any of the K elements chosen is less than every M elements.

Example

input:N_a=5,N_b=2,K=3,M=1 

 A=[1,1,1,1,1] 

B=[2,2]  

output:true  

explanation:K chosen elements from Array A->[1,1,1] M chosen elements from Array B->[2,2] 

input:N_a=3,N_b=3,K=2,M=1 

A=[1,2,3] 

 B=[3,4,5] 

output:true  

explanation:K chosen elements from Array A->[1,2] M chosen elements from Array B->[3] 

input:N_a=3,N_b=3,K=3,M=3

A=[1,2,3]

B=[3,4,5] 

output:false

Approach:In this problem we need to check if every chosen K elements is less than every chosen M elements.So if we observe carefully , we have to check if the K_th smallest element of the Array A is smaller than the M_th largest element of the Array B,if its true then our output will be true (because the elements smaller than K_th smallest will also be less than M_th largest),else false.

Solution

Below is the Java implementation of the above approach

Code

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

class Solution{
    public static boolean check(int[] a, int[] b, int Na,
                                 int Nb, int k, int m)
    {
        // Sorting Both the arrays
        // to find Kth smallest and
        // Mth largest
        Arrays.sort(a);
        Arrays.sort(b);
        // if kth smallest is less
        // than mth largest
        // return true
        if (a[k - 1] < b[Nb - m]) {
            return true;
        }
        // else return false
        return false;
    }
    // driver Code
    public static void main(String[] args)
    {
        int Na = 3;
        int Nb = 3;
        int k = 2;
        int m = 1;
        int[] a = { 1, 2, 3 };
        int[] b = { 3, 4, 5 };
        // Calling function
        System.out.println(check(a, b, Na, Nb, k, m));
    }
}

Output:

true

Time Complexity:if N_a>N_b then->O(N_a log N_a),else O(N_b log N_b)

Auxiliary space:O(1)

Feel free to comment if you have any doubt in comment section

For more Data structure and algorithms,computer science,programming,coding related problems search my website.


Learn how to prepare for Information Technology Based companies here