Find the K-th Smallest Element in Array

Easy
0/40
Average time to solve is 10m
profile
Contributed by
10 upvotes
Asked in companies
MicrosoftFlipkart limitedBlackrock

Problem statement

You are given an array/list ‘ARR’ consisting of ‘N’ non - negative integers and an integer ‘K’. Your task is to return the K-th smallest element of the array.

For example :-

Given an array/list ‘ARR' = [ 3, 2, 4, 5, 6 ] and 'K' = 3. The 3rd smallest element is "4" because the order of numbers is [ 2, 3, 4, 5, 6 ].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘T’ lines represent the ‘T’ test cases.
The first line of input contains two space-separated integers ‘N’ and ‘K’. 
The second line of input contains the ‘N’ space-separated integer which denotes the element of array ‘ARR’.
Output Format: 
For every test case, print the ‘K-th’ smallest element in the array 'ARR'.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraint : 
1 <= T <= 100
1 <= K <= N <= 5000
-10^9 <= ARR[i] <= 10^9


Where ‘T’ represents the number of test cases, ‘N’ is the number of elements in array ‘ARR’ , ‘K’ denotes an integer. ‘ARR[i]’ represents the value of the number at ‘i’ position in ‘ARR’.

Time Limit: 1 sec
Sample Input 1:
2
5 2
4 5 3 7 6
6 3
5 2 1 4 3 6
Sample output 1:
4
3
Explanation For Sample Input 1:
In the first test case, ‘ARR' = [ 4, 5, 3, 7, 6 ] and ‘K' = 2. Then 2nd smallest element is ‘4’ because the order of numbers is [ 3, 4, 5, 6, 7].
In the second test case, ‘ARR’ = [ 5, 2, 1, 4, 3, 6 ] and ‘K’ = 3. Then 3rd smallest element is ‘3’ because the order of numbers is [ 1, 2, 3, 4, 5, 6 ].
Sample Input 2:
2
3 2
-1 -2 6
4 4
4 5 2 1
Sample output 2:
-1
5
Explanation For Sample Input 2:
In the first test case, ‘ARR' = [ -1, -2, 6 ] and ‘K' = 2. Then the 2nd smallest element is ‘-1’ because the order of numbers is [ -2, -1, 6].

In the second test case, ‘ARR’ = [ 4, 5, 2, 1] and ‘K’ = 4. Then the 4th smallest element is ‘5’ because the order of numbers is [ 1, 2, 4, 5 ].
Hint

Can we use sorting to solve this problem?

Approaches (3)
Sorting

Approach: The key idea is to sort the whole array in ascending order. The smallest element will be at index ‘0’ and the second smallest element at index ‘1’ and likewise, the ‘K’th smallest element will be at the ‘K - 1’th index.

 

The algorithm will be-

  1. Sort the given array ‘ARR’.
  2. Return ‘ARR[K - 1]’.

 

Time Complexity

O(N*log(N)), Where ‘N’ is the number of elements in array ‘ARR’.

 

The time complexity due to sorting will be O(N * log(N)).

Space Complexity

O(1), We are using constant space.

Code Solution
(100% EXP penalty)
Find the K-th Smallest Element in Array
Full screen
Console