kth Smallest Element

Problem Statement

We are given an integer array nums and an integer k. We have to return the kth smallest element in the array where $k <=$ size of nums. Also, note that we have to return the $kth$ smallest element not the kth distinct element.

Example

Example Explanation

If we sort the above array, this will lead us to an array,
$1,2,4,5,5,6,9,12,56$
In the above-sorted array, the $1st$ smallest element is 1, the $2nd$ smallest element is 2, the $3rd$ smallest element is 4, the $4th$ smallest element is 5, the $5th$ smallest element is 5, ...., the $9th$ smallest element is 56.

So the $4th$ smallest element is 5, hence the output of the program should be 5.

Constraints

If n is the number of elements in nums then,
$1 <= k <= n <= 10^4$
and if $nums[i]$ represents the $ith$ element of the nums array then,
$-10^4 <= nums[i] <= 10^4$

Approach - 1 : Brute Force, Using Sorting

We will consider the same example we used above,

Then the sorted version of the above array will look like this,

Notice here, the $0th$ index is having $1st$ smallest element $i.e$ 1,
the $1st$ index is having the $2nd$ smallest element $i.e$ 2,
the $2nd$ index is having the $3rd$ smallest element $i.e$ 4,
and so on.

So after sorting the array, the $kth$ smallest element is at $(k-1)th$ index.

Algorithm

• Sort the array in increasing order.
• Return the element present at $(k-1)th$ index as the array is $0-indexed$.

Code Implementation

C++ :

Output :

Java :

Output :

Python :

Output :

Time Complexity

Since we are sorting the array, we can use Heap Sort and the worst time complexity for sorting the array is $O(NlogN)$, and then we are returning the $(k-1)th$ index in $O(1)$. Therefore time complexity of the above algorithm is, $O(NLogN)$.

Space Complexity

As we are using Heap Sort and Heap Sort doesn't require any extra space, therefore the space complexity is, $O(1)$.

Approach - 2 : Using Set from C++ STL

If the elements of nums are distinct, then we can use sets to find the $kth$ smallest element as set in C++ STL stores the element in sorted order. As the elements are in sorted order, therefore we can use this property for finding the $kth$ smallest element. But there's a constraint that the elements of nums should be distinct.

As we have to find the $kth$ smallest element, then we have to skip the first $(k-1)$ elements as the elements in the set are sorted. Like in the above example where the $1st$ smallest element is at 0.

Algorithm

• Insert all the elements of the nums into a set.
• Initialize an iterator to the beginning of the set.
• Advance the iterator to the $kth$ element by skipping the first $(k-1)$ elements as the elements are sorted.

Code Implementation

C++ :

Output :

Time Complexity

A Set in C++ STL takes $O(LogN)$ time for insertion in the worst case and we are inserting all the elements of nums to the set. Therefore the time complexity of this approach is $O(NLogN)$.

Space Complexity

Since we are using a set and storing the elements of the nums in the set, the space complexity is $O(N)$ for the extra set used.

Approach - 3 : Using Min-Heap

As we are interested in the smallest or minimum element, think of a data structure that can help us to get the smallest or minimum element in the best time. You guessed it right, it's min-heap. Min heap stores elements in increasing order, hence the smallest element is at the top of the min-heap.

Now heaps itself is a vast topic and you can learn more about heaps here at Heap Data Structure.

For the time being, we will be assuming that you are familiar with the working of heaps and we will be using a priority queue.

Algorithm

• Build the min-heap by passing all the elements of nums to the min-heap. So the size of the min-heap will be equal to the size of nums.
• Pop $(k-1)$ elements from the min-heap.
• $Kth$ smallest element is at the top of the min-heap.

Code Implementation

C++ :

Output :

Java :

Output :

Python :

Output :

Time Complexity

An insertion in min-heap takes $O(LogN)$ in the worst case. We are inserting N elements in the min-heap. Therefore the time complexity of inserting N elements in a min-heap is $O(NLogN)$.

Also min-heap takes $O(1)$ to pop an element from the heap and we will be popping $(K-1)$ elements from the heap. So the overall time complexity of this approach is $O(NLogN + KLogN)$.

Space Complexity

Since we will be storing N elements in the min-heap, therefore the space complexity is $O(N)$ for the extra space used by Min-Heap.

Approach - 4 : Using Max-Heap

Max-heap has the property of storing max element at the top, so we can use this property. Instead of thinking of the problem like kth smallest element, think it of as the maximum element out of $k$ minimum elements. Like, consider the same array, here the $k$ minimum elements for $k=4$ are,
$1, 2, 4, 5$
Out of these elements, 5 is the maximum therefore 5 is our answer.

Let $k = 6$ then the k minimum elements are,
$1, 2, 4, 5, 5, 6$
Now our answer is 6.

We will store only k elements in the heap and will iterate over the remaining elements. If the current element is less than the top of the heap, it means we have to include this element in the heap. At the end of the iteration, we will be having a heap of k elements and the $kth$ smallest element is at the top of the heap.

The above image demonstrates the state of the heap when we start at the ith index. For the $4th$ index, the top element of the heap is 12, and 56 was the current element. Since $56>12$, we skipped this element. At $i=5$ the current element is 5 and $5<12$, therefore we popped 12 and pushed 5 into the max-heap.

Algorithm

• Push first k elements into the max-heap.
• Iterate over the remaining elements of nums. If the current element $<$ top of the heap, pop the top element from the heap and push the current element into nums. So at any time, there will be only k elements in the max-heap.
• $Kth$ smallest element is at the top of the heap.

Code Implementation

C++ :

Output :

Java :

Output :

Python :

Output :

Time Complexity

As we build the heap with K elements, and then iterate over $N-K$ elements and push them to the max-heap. Therefore the time complexity is $O(K + (N-K)LogK)$. $O(K)$ for building the max-heap of K elements and for the remaining $(N-K)$ elements it can take upto $O(LogK)$for the insertion of each element in the max-heap. So overall time complexity is $O(K + (N-K)LogK)$.

Space Complexity

At any instant, we will be storing k elements in the heap, therefore space complexity is $O(K)$.

Approach - 5 : Using Quick Select

As the name implies Quick Select is similar to Quick Sort. Quick Sort selects a pivot element, moves it to the right location, and partitions the surrounding array such that the elements smaller than the pivot are on the left side, and elements greater than the pivot are on the right side. But unlike quick sort where we process both sides of the array, here we will only process one side of the array.

We process either the left side of the pivot element or the right side of the pivot as we are only interested in the case where the pivot is our kth smallest element. When the pivot is our $kth$ smallest element, the index of pivot will be $(k-1)$ as we checked above in the case of sorting. When we finish the processing for pivot or $kth$ smallest element, it means there are $(k-1)$ elements smaller than the pivot hence our $kth$ smallest element is the pivot.

Algorithm

Considering l is the lower index of the array and h is a higher index of the array :

• Partition the array around the pivot and return the index of the pivot.
• If index of pivot : $l == k-1$ then the $kth$ smallest element is at index of pivot as there are $(k-1)$ elements lesser than the pivot.
• If index of pivot : $l > k-1$, then we should process the left side as the index of pivot is greater.
• Else we should process the right side of the array as the index of pivot is smaller.

Code Implementation

C++ :

Output :

Java :

Output :

Python :

Output :

Time Complexity

The average case time complexity is $O(N)$ and the worst-case time complexity is $O(N^2)$ when the elements of $nums$ are in decreasing order and we choose the rightmost element as the pivot.

Space Complexity

Since we are using recursion and in each step of the recursion we either proceed with the left side or right side of the array. Therefore with each step, our problem is reduced by half. Hence the space complexity is $O(LogN)$ for the recursion stack space.

Approach - 6 : Using Binary Search

If we look at approach 1, we can notice that the $k^{th}$ smallest element is at the $k-1^{th}$ index. Let $x$ be the $k^{th}$ smallest element, so there will be at least k elements (including $x$) that are less than or equal to x. We will use binary search to predict the element's position in a sorted array without actually sorting the array.

Consider the array,
$9,6,1,12,56,5,4,2,5$
and
$k = 4$
We have to find an element that has k elements (including self) lesser to it. In the above case for element 5, there are 3 elements lesser than 5 and these are $4,2,1$ if we include 5 this will lead us to k. Therefore 5 is the $kth$ smallest element.

Let's understand how we will proceed with binary search in this problem, We will iterate over $[$min of nums, max of nums$]$ and for each mid in the range we will check whether the number of elements less than or equal to mid is k or not.

If the mid's count $< k$, it means that we need to increase mid so that count can also increase.

In the other case if mid's count $> k$, we need to decrease the mid so that the count can also decrease.

The yellow block contains the cases where mid's count $> k$, here 4. And the blue contains the case where mid's count $<= k$.

Algorithm

Considering $l$ is the minimum element of the array and $h$ is a maximum element of the array :

• Perform the following operation while $l<h$,
• Calculate mid by $l+(h-l)/2$.
• Check if mid can be the kth smallest element by counting the that have value less than or equal to mid.
• If $count$ $< k$ then set $l = mid+1$ as the count is less than k and we need to increase the mid so the count can be equal to k, else set $h = mid$, so that count can be decremented to k.
• At the end of the while loop, l will be storing the $kth$ smallest element of the array.

Code Implementation

C++ :

Output :

Java :

Output :

Python :

Output :

Time Complexity

If $l$ is the minimum element and h is the maximum element of the array, then the time complexity is $O(N*Log(h-l))$ as we are performing binary search over the range $[l, h]$ and each iteration costs $O(N)$ for count function.

Space Complexity

Since we are not using any other data structure except the nums array, the space complexity is $O(1)$.

Approach - 7 : Using Map

If we create a map of elements of the nums with their frequencies, and as the map stores data in an ordered way. Therefore we can iterate over the frequencies of the elements and if, at any instant sum of frequencies $>= k$, the $kth$ smallest element will be the key to the current mapping.

Consider the array,
$9,6,1,12,56,5,4,2,5$
and
$k = 4$

In the above image we can see that for key $= 5$, we have freq $= 5$ which is greater than k. Therefore 5 is the $kth$ smallest element.

Algorithm

• Map all the elements of the nums with their frequencies.
• Declare a freq $= 0$ variable and iterate over the mapping in the map, for each mapping add the frequency to freq.
• If freq$>=k$, the kth smallest element is the key to the current mapping and breaks the loop.

Code Implementation

C++ :

Output :

Java :

Output :

Time Complexity

Since we are interested in the sorted order of the elements in the map, we are using map in C++ and TreeMap in Java. Both these maps take $O(LogN)$ time for inserting an element. Therefore for N elements the time complexity is $O(NLogN)$. Then we iterate over K values in the map, therefore overall time complexity of this approach is $O(NLogN + K)$

Space Complexity

As we are storing N elements in the map, therefore the space complexity is $O(N)$.