# 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 and Nb 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:Na=5,Nb=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:Na=3,Nb=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->

input:Na=3,Nb=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 Kth smallest element of the Array A is smaller than the Mth largest element of the Array B,if its true then our output will be true (because the elements smaller than Kth smallest will also be less than Mth 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 Na>Nb then->O(Na log Na),else O(Nb log Nb)

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