Last Updated: 17 Feb, 2021
Kth smallest element in an unsorted array
Moderate
Asked in companies
Given an unsorted array ‘arr’ of distinct integers and an integer ‘k’, your task is to find the ‘k-th’ smallest element in the array.
Example:
n = 5, k = 2 and arr[] = {6, 5, 4, 8, 7}
The array elements in sorted order are [4, 5, 6, 7, 8]. The ‘2-nd’ smallest element in the array is 5, so the answer is 5.
Note:
1. Don’t print anything. Return the value of ‘k-th’ smallest element.
2. ‘k’ is a positive integer and not greater than the size of the array.
3. The array ‘arr’ is unsorted, and all the elements of the array are distinct.
Input format:
The first line of 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’, where ‘n’ is the array’s size.
The second line of each test case contains ‘n’ space-separated integers denoting the array elements.
Output format:
For each test case, return the ‘k-th’ smallest element in the array.
Output for each query is printed in a separate line.
Constraints:
1 <= T <= 10
1 <= n <= 1000
1 <= k <= n
-10^6 <= arr[i] <=10^6
Where ‘T’ is the total number of test cases, ‘n’ denotes the array’s size, ‘k’ denotes the ‘k-th’ smallest element that you must return, and ‘arr[i]’ denotes the range of elements in the array.
Time limit: 1 second
Approaches
If we sort the given array in ascending order, then the required answer would be the element at index ‘k’ in the sorted array.
- Sort the given array in ascending order.
- The ‘k-th’ element (at index ‘k-1’) in the array will be the ‘k-th’ smallest element, return it as the final answer.
We will first create a min-heap of the given array elements. After that, we use the extract-min operation on the min-heap ‘k-1’ times to remove the smallest ‘k-1’ elements of the array. Then the root stores the ‘k-th’ smallest element of the array.
Heapify: This function rearranges the subtree elements with the root at the given index to maintain that subtree’s heap property (i.e., for min-heap, the root’s key is smaller than or equal to the keys of its children). For a min-heap, if the root’s key is not the smallest of its children, then swap it with the smallest child key, then recursively call ‘heapify’ for that child’s subtree. The child subtrees must obey the heap property for the correct working of this function.
- Run a for loop where ‘i’ ranges from ‘(n-1)/2’ to 0. Call the function ‘heapify’ with parameter ‘i’.
- Run a for loop where ‘i’ ranges from 0 to ‘k-2’. In this loop, call the ‘extractMinElement’ function to remove the smallest element from the heap.
Return the root of min-heap (i.e., ‘arr[0]’), which is the ‘k-th’ smallest element.
We will first create a max-heap of the first ‘k’ elements (i.e., ‘arr[0]’ to ‘arr[k-1]’) from the given array. Then we iterate each element from ‘arr[k]’ to ‘arr[n-1]’ and compare it with the root of the max-heap. If it’s smaller than the root, we make it root and call the ‘heapify’ function with parameters as root. Finally, the max-heap contains the smallest ‘k’ elements of the array, and the root of the max-heap stores the ‘k-th’ smallest element of the array.
Heapify: This function rearranges the subtree elements with the root at the given index to maintain that subtree’s heap property (i.e., for max-heap, the root’s key is greater than or equal to the keys of its children). For a max-heap, if the root’s key is not the greatest of its children, then swap it with the greatest child key, then recursively call ‘heapify’ for that child’s subtree. The child subtrees must obey the heap property for the correct working of this function.
- Run a for loop where ‘i’ ranges from ‘(k-1)/2’ to 0. Call the function ‘heapify’ with parameter ‘i’.
- Run a for loop where ‘i’ ranges from ‘k’ to ‘n-1’. We compare the root of the heap (i.e., ‘arr[0]’) with ‘arr[i]’. If ‘arr[i]’ is smaller than the root then ‘arr[0]’ = ‘arr[i]’ and we call the ‘heapify’ function with parameter 0.
- The root of the max-heap (i.e. ‘arr[0]’) stores the ‘k-th’ smallest element. Return ‘arr[0]’ as the final answer.