Last Updated: 26 Jan, 2021
Find the K-th Smallest Element in Array
Easy
Asked in companies
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 ].
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
Approaches
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-
- Sort the given array ‘ARR’.
- Return ‘ARR[K - 1]’.
Approach: The basic idea is that, create a min-heap and insert all the elements in the min-heap one by one. In the end, pop K elements one by one, so the ‘K-th’ element will be the answer as every time the smallest element will be popped out from the minHeap.
The algorithm will be:
- Create a min-heap ‘MINHEAP’ from the elements of the ‘ARR’.
- Now for 'i' from 1 to ‘K - 1'
- Pop-out the top element of the ‘MINHEAP’.
- We finally return the topmost element of the ‘MINHEAP’.
Approach: The basic idea is that, try to maintain a max-heap of size ‘K’. We will initially create a max heap from ‘K’ elements. Then for the remaining ‘N - K’ elements, we will either insert it in the ‘maxHeap’ depending on whether it is less than the top of the ‘maxHeap’.
The properties of max-heap are -
- We can access the maximum element of the max-heap in constant time.
- We can delete an element in O(log(K)) time complexity, where ‘K’ is the number of elements which is already present in the heap.
- We can add an element in the max-heap in O(log(K)) time complexity.
The algorithm will be-
- We use a max-heap named ‘MAXHEAP’.
- Now, for each ‘i’ from ‘0’ to ‘K - 1’ (both ‘0’ and ‘K - 1’ are inclusive)
- Add ‘ARR[i]’ in the ‘maxHeap’.
- Now, for each ‘i’ from ‘K’ to ‘N - 1’(both ‘K’ and ‘N - 1’ are inclusive):
- If ‘ARR[i] < ‘TOP’ of 'MAXHEAP’:
- Delete the top element and add ‘ARR[i]’ in the maxHeap as the top element of the ‘MAXHEAP’ can’t be a part of the ‘K’ smallest elements of the array.
- If ‘ARR[i] < ‘TOP’ of 'MAXHEAP’:
- We finally return the ‘TOP’ element of the ‘MAXHEAP’.