# Find K’th smallest element in an array

Given an array and positive integer k, find k’th smallest element in the array.

For example,

Input:

arr = [7, 4, 6, 3, 9, 1]
k = 3

Output:

k’th smallest element in the array is 4

#### Approach 1 (Sorting) –

A simple solution would be to use an efficient sorting algorithm to sort the array in ascending order and return the element at (k-1)th index. The worst case time complexity of this approach will be O(nlogn) where n is the size of the input array.

#### Approach 2 (Using Max Heap) –

We can easily solve this problem in O(nlogk) by using a max-heap. The idea is to construct a max-heap of size k and insert first k elements of array (A[0..k-1]) into the heap. Then for each of the remaining element of the array (A[k..n-1]), if that element is less than the root of the heap, we replace the root with current element. We repeat this process till array is exhausted. Now we will be left with k smallest elements of the array in the max-heap and k’th smallest element will reside at the root of the max-heap.

## Java

Output:

K’th smallest element in the array is 4

#### Approach 3 (Using Min Heap) –

We can easily solve this problem in O(n + klogn) by using a min-heap. The idea is to simply construct a min-heap of size n and insert all elements of the array (A[0..n-1]) into it. Then we pop first k-1 elements from it. Now k’th smallest element will reside at the root of the min-heap.

## Java

Output:

K’th smallest element in the array is 4

#### Approach 4 (Using std::nth_element) –

We can easily solve this problem by using std::nth_element. The prototype of std::nth_element is –

void nth_element (RandomAccessIterator first, RandomAccessIterator n, RandomAccessIterator last);

It rearranges the elements in the range [first,last), in such a way that the element at the n’th position is the element that would be in that position in a sorted sequence.

std::nth_element is typically implemented using a fancy version of quickselect called introselect. You can imagine quickselect as a version of quicksort where the recursive call is only executed on the side which contains the element. Introselect ensures the worst-case linear running time if quickselect takes too long (bad pivot selection). It basically switches to an algorithm with worst-case O(n) time, which is slower in most cases but saves the day when quickselect has trouble.

C++ implementation –

Output:

K’th smallest element in the array is 7

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon

Subscribe
Notify of
Guest

I don’t think your analysis for the min-heap solution is correct. We first have to insert each of the n elements, with time logarithmic for each element; so the proper runtime would actually end up being O(n log n + k log n) = O(n log n)

Guest