How To Find The Kth Smallest Element In An Array?

How To Find The Kth Smallest Element In An Array?
How To Find The Kth Smallest Element In An Array?

Introduction

Let’s say, You have to find out the smallest, 2nd smallest, and then the 3rd smallest number of the six numbers above. It seems to be an effortless task to achieve. In programming, you must have come across problems asking you to find the 2nd smallest number from a group of numbers.

As you can think of, it is a pretty straightforward task. You choose any two numbers and start comparing them with the rest of the element. If we find a number smaller than one or both of them, we remove the greater number.

By this method, we end up with the two smallest numbers in the group after complete traversal of it.


Now, consider you are given a group of distinct numbers and asked to find the kth smallest number out of them, you can still use the above method, but that won’t be viable if k is a sufficiently large number.

So for that, we have listed a few methods you can use to achieve this task efficiently. Though most of the methods use the idea of sorting first, we have kept some methods to find the kth smallest element in an array without sorting. Keep a check on the time complexity of each approach to understanding which one is best suited for this task.

Finding the kth smallest element in an array with sorting

To begin with, we will use the method with the simplest implementation. So, if you are given an unsorted array with distinct values and asked to print its kth smallest element, the easiest thing you can do is sort it and then return the element at the k-1th position(Considering 0-Based indexing).

To execute this, We first sort the array then access its k-1th index, which contains the kth smallest element of the array.

Let’s have a look at the implementation of this method:

#include<bits/stdc++.h>
using namespace std;
//Function to sort the array then return the element on index k-1.
//It takes an array, its size, and a number k as arguments.
int tofindkthsmallest(int array[], int n, int k)
{
    sort(array,array+n);
    return array[k-1];
}
// Driver function.
int main()
{
    int array[] = {50,10,75,55,45};
    int n = sizeof(array) / sizeof(array[0]), k = 2;
    cout << "K'th smallest element is " << tofindkthsmallest(array, n, k);
    return 0;
}

Output:

K'th smallest element is 45.

The time complexity of this method is O(N*logN) because of the sorting algorithm used in it.

The space complexity of the method depends on the sorting algorithm used. For example, It’ll be O(N) if we use merge sort and O(1) if we use heap sort.

Finding the kth smallest element in an array using set in STL

So, in this approach, we will be using a set container from the C++ Standard Template Library (STL), which takes key values and pushes them in the set in sorted order by default.

This method works only when your array doesn’t contain duplicate elements. We move all the elements in the set, then traverse the set to print the kth element.

We start with pushing all the array elements in the set, then traverse through the set and return its k-1th element, which will be the kth smallest element of the array.

Let’s have a look at the implementation of this method:

#include <bits/stdc++.h> 
using namespace std; 
//Function to push the elements of the array into the set then traverse and print the kth element.
//It takes an array, its size, and a number k as arguments.
int tofindkthsmallest(int array[], int n, int k) 
{ 
    set<int> s; 
    for (int i = 0; i < n; i++) 
      {  s.insert(array[i]); }
 
    auto it = s.begin(); 
    for (int i = 0; i < k - 1; i++) 
      {  it++; }
 
    return *it; 
} 
//Driver function.
int main() 
{ 
    int array[] = { 50,10,75,55,45 }; 
    int n = sizeof(array) / sizeof(array[0]), k = 2; 
    cout << "K'th smallest element is "
         << tofindkthsmallest(array, n, k); 
    return 0; 
} 

Output:

K'th smallest element is 45

The time complexity of this method is O(N*logN) because the set in STL uses self-balancing BST for implementation, in which insert and search operations take place in O(logN) time. So, the corresponding time complexity will be O(N*logN) for inserting all the N elements. 

The space complexity will be O(N). 

Finding the kth smallest element in an array using Min heap-

A better solution to this problem is possible using min-heap. The root is always the minimum element in the min-heap, so we extract the root and rebuild the min-heap for the k times. That’s when the top element is the kth smallest element in the array used to form the min-heap.

We start with building a min-heap of all the elements in the array. Then Extract the minimum element for k-1 times. The final step is to return the root of the min-heap, which will be the kth smallest element of the array.

Let’s have a look at the implementation of this method:

#include<bits/stdc++.h>
using namespace std; 
  
//Function to swap two integers.
void swap(int *x, int *y)
{ 
    int temp = *x; 
    *x = *y; 
    *y = temp; 
} 
  
//Create a class for min-heap.
class minh 
{ 
    // pointer to array containing elements of the heap.
    int *harray; 
    // maximum number of elements min heap can hold.
    int cap;
    // number of elements present in min heap. 
    int h_size;  
public: 
    // Constructor for the min heap. 
    minh(int a[], int size);
    //To minheapify subtree with index i as root.     
    void minheapify(int i);  
    int parent(int i) { return (i-1)/2; } 
    int left(int i) { return (2*i + 1); } 
    int right(int i) { return (2*i + 2); } 
    // To extract root element, which is the minimum element. 
 
    int extractMin(); 
    // Returns minimum 
    int getMin() { return harray[0]; } 
}; 
  
minh::minh(int a[], int size) 
{ 
    h_size = size; 
    harray = a; 
    int i = (h_size - 1)/2; 
    while (i >= 0) 
    { 
        minheapify(i); 
        i--; 
    } 
} 
  
// Method to remove root of the min heap i.e. the minimum element. 
int minh::extractMin() 
{ 
    if (h_size == 0) 
        return INT_MAX; 
  
    // To store that value
    int root = harray[0]; 
  
    if (h_size > 1) 
    { 
        harray[0] = harray[h_size-1]; 
        minheapify(0); 
    } 
    h_size--; 
  
    return root; 
} 
  
// To recursively heapify a subtree with the root at a given index, it also assumes that the subtrees are already heapified.
void minh::minheapify(int i) 
{ 
    int l = left(i); 
    int r = right(i); 
    int smallest = i; 
    if (l < h_size && harray[l] < harray[i]) 
        smallest = l; 
    if (r < h_size && harray[r] < harray[smallest]) 
        smallest = r; 
    if (smallest != i) 
    { 
        swap(&harray[i], &harray[smallest]); 
        minheapify(smallest); 
    } 
} 
  
 
// Function to return k'th smallest element in a given array. 
int tofindkthSmallest(int arr[], int n, int k) 
{ 
    // To build a heap of n elements.
    minh mh(arr, n); 
  
    // To extract the minimum element (k-1) times.
    for (int i=0; i<k-1; i++) 
        mh.extractMin(); 
  
    // To return the root that is the kth minimum element. 
    return mh.getMin(); 
} 
  
// Driver Function.
int main() 
{ 
    int arr[] = {50,10,75,55,45}; 
    int n = sizeof(arr)/sizeof(arr[0]), k = 2; 
    cout << "K'th smallest element is " << tofindkthSmallest(arr, n, k); 
    return 0; 
} 

Output:

K'th smallest element is 45

The time complexity of this approach is- O(N+klogN) as we are building a min-heap of n elements which takes O(N) time and extracting minimum elements for k times, where extracting(popping) a minimum from the heap takes O(logN) time. 

The space complexity of this method is O(N) as we build a heap of n elements.

Finding the kth smallest element in an array using Max heap-

Finding the kth smallest element in an array can be done more efficiently using the max heap. In a max heap, the element on the top is always the maximum element. It also uses the idea similar to the concept of maintaining k variables to store k smallest numbers,  but using max heap makes it viable even for large values of k.

We build a Max heap of first k elements to find the kth smallest element in an array using a priority queue. Check the rest of the elements one by one. If they are smaller than the top, we replace the top with the current element.

The heap rearranges itself to bring the greatest element on the top. Once we have checked all the elements, the top of the max heap is the kth smallest element in the array.

Let’s have a look at the implementation of this method:

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the k'th smallest element in an array using max-heap.
int tofindKthSmallest(vector<int> const &v, int k)
{
    // We will start with inserting the first `k` elements of the  array into Max-heap created using `std::priority_queue.`
 
    priority_queue<int, vector<int>> pqueue(v.begin(), v.begin() + k);
 
    // For the remaining elements in the array.
    for (int i = k; i < v.size(); i++)
    {
        // If the root of the heap is greater than current element.
        if (v[i] < pqueue.top())
        {
            // Current element will be replaced by the root.
            pqueue.pop();
            pqueue.push(v[i]);
        }
    }
 
    // To return the root of max-heap.
    return pqueue.top();
}
//Driver function.
int main()
{
    vector<int> input = { 50,10,75,55,45};
    const size_t k = 2;
 
    cout << "The kth smallest array element is " << tofindKthSmallest(input, k);
 
    return 0;
}

Output:

The kth smallest array element is 45

The time complexity of this method is O(K + (n-k)*log(k)). Because we are building a max heap of k elements and then checking the remaining (n-k) elements into the top of the heap.

The space complexity of this method is O(k) as we build a heap of k elements.

Finding the kth smallest element in an array using Quickselect

Apart from all the above approaches, we have another method that performs this task most efficiently in average cases. This approach uses the idea of partition from Quicksort. We need to modify its procedure. 

It picks a pivot then partitions the array around it. It keeps repeating the process until the index of the Pivot is the k-1. This method becomes highly efficient because we drop off one of the subarrays formed after partitioning, which has no probability of containing the kth smallest element.

Let’s have a look at the implementation of this method:

#include <bits/stdc++.h>
using namespace std;
 
//Function to swap two integers.
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
} 
// Partition function of QuickSort(). It takes the last element as Pivot and rearranges the array so that Pivot is at its right place with all smaller to its left and greater elements to its right.
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
} 
// This function finds and returns the kth smallest element in arr[l to r] using the above partition function.
int tofindkthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1) {
    // Call the Partition function on the array with last element as pivot, it will return the index of pivot element in the sorted array.
        int pos = partition(arr, l, r);
 
        // If index of pivot is same as k.
        if (pos - l == k - 1)
            return arr[pos];
        // If Index of Pivot is greater, recur for left subarray.
        if (pos - l > k - 1) 
            return tofindkthSmallest(arr, l, pos - 1, k);
 
        // Else recur for right subarray.
        return tofindkthSmallest(arr, pos + 1, r, k - pos + l - 1);
    }
 
    // If k is greater than no. of elements in the array.
    return INT_MAX;
}
 
// Driver Function.
int main()
{
    int arr[] = {50,10,75,55,45};
    int n = sizeof(arr) / sizeof(arr[0]), k = 2;
    cout << "Kth smallest element is " << tofindkthSmallest(arr, 0, n - 1, k);
    return 0;
}

Output:

Kth smallest element is 45

The time complexity of this method is O(N^2)  in the worst case but, if we choose the Pivot randomly, it becomes O(N) on average. 

The space complexity of this method is O(LogN) in the average case and O(N) in the worst case. To read in detail, check QuickSelect here.

Frequently Asked Questions

Can we find the kth smallest element in an array of size n using min-heap?

Yes, we can find the kth smallest element in an array of size n using min-heap.

How do you find the kth largest element in an unsorted array?

There are many ways to do it as discussed above, where the most basic approach is to sort the array in ascending order. The element at index n-k will be the kth largest element in that array.

What is the name of the algorithm that is able to find the kth smallest element in an unordered list?

In computer science, a selection algorithm is for finding the kth smallest number in a list or array; such a number is called the kth order statistic.

How do you find the kth smallest element in an unsorted array in Python?

Sort the array using any sorting technique in descending order. 2. Iterate through the array till you reach the K-th element and then print the value at the K-th index.

What is the kth smallest element?

The kth smallest element is the minimum possible n such that there are at least k elements in the array <= n.

Key Takeaways

In this blog, we learned how to find the kth smallest element in a given array.

  • The first method was to sort the array and return the element at the k-1th index. 
  • The second method used the set from STL. In this method, we pushed all the array elements into the set and then traversed to its k-1th element. 
  • The third method used min-heap, forming a min-heap of n elements then extracting its root element for k times, returns the kth smallest element of the array. 
  • The fourth method used max-heap, creating a max-heap of the first k elements in the array, then the top is compared with all remaining elements of the array. Smaller elements replace the top and get inserted into the heap. After all the elements, the top returns the kth smallest element. 
  • The last method used the QuickSelect algorithm to solve the problem. We partition the array as done in quicksort, drop one of the two resultant subarrays, and repeat this step until the pivot’s correct position is equal to k-1.

Check out more blogs on the sorting of arrays, the heap data structure to read more about these topics in detail. And if you liked this blog, share it with your friends!

By Gorakhnath Yadav

Exit mobile version