K'th smallest/largest element in an array

Easy

0/40

135 upvotes

Asked in company

Problem statement

Given an array and a number K where K is smaller than size of array, we need to find the K'th smallest element and K'th largest element in the given array. It is given that all array elements are not distinct.

Note:

If element is not present, then return -1.

K'th largest and smallest element in the sorted array. You are given an array consisting of N non distinct positive integers and a number K, your task is to find the K'th largest and K'th smallest element in the array.

1) Kth largest and smallest element in an array is the K'th element of the array when sorted in increasing order. For example consider the array {2, 1, 5, 6, 3, 3, 8} and K=4, the sorted array will be {1, 2, 3, 3, 5, 6, 8}. But we will check the array {1, 2, 3, 5, 6, 8} as 3 is repeated twice and the 4th largest element will be 3 and 4th smallest will be 5.

2) All the elements of the array are not distinct.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two space-separated integers N and K, as described in the problem statement.

The second line of each test case contains N space-separated integers, representing the elements of the array.

Output Format:

The only line of output prints the K'th largest and K'th smallest element separated by space.

Constraints:

1 <= T <= 100
1 <= N <= 10^3
1 <= arr[i] <= 10^9
1 <= K < N

Sample Input 1:

1
3 2
1 2 3

Sample Output 1:

2 2

Explanation for sample input 1:

2 is the second largest and second smallest element in an array {1,2,3}.

Sample Input 2:

1
3 2
5 5 5

Sample Output 2:

-1 -1

Explanation for sample input 2:

Since there is only 1 unique element therefore second largest and second smallest element does not exist hence -1.

Approaches (1)

Approach 1

Iterative Approach

We first sort the Array so that we can access the K smallest elements at the beginning and K largest elements at the end.
We keep a counter to store the number of distinct elements encountered till now.
As soon count reaches K we print the current element and break.
Similarly, we do it for the Kth largest element as well.
If our counter remains < K after the whole loop we report that answer doesn't exist and print -1.

Time Complexity

Space Complexity

(100% EXP penalty)

K'th smallest/largest element in an array

Console