Problem link :- Choose K numbers in
Problem Statement:
You are given two arrays A and B, both sorted in non-decreasing order. Your task is to check if it is possible to choose k numbers from array A and m numbers from array B such that every number chosen from array A is strictly less than any number chosen from array B.
Approach:
The key idea is to compare specific elements from arrays A and B to determine if the condition can be met. Since both arrays are sorted, the smallest k elements in A will be in the first k positions, and the largest m elements in B will be in the last m positions.
- Input the arrays: First, read the sizes of the arrays nA (for A ) and nA (for B), followed by reading the arrays themselves. You also read the values k and m which specify how many elements to select from A and B respectively.
- Compare elements: To satisfy the condition that all chosen numbers from A are strictly less than those from B, we compare the k-th smallest element in A (which is A [k-1] because array indices are 0-based) with the m-th largest element in B (which is B[nB-m]).
- Check the condition: If A[k-1] (the k-th smallest element in A) is strictly less than B[nB-m] (the m-th largest element in B), we output “YES”. Otherwise, we output “NO”.
Time Complexity:
O(nA + nB) – We read and process both arrays in linear time.
Space Complexity:
O(1) – As no additional space is used.