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.
Implementation of array using set in STL
C++
#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;
}
You can also try this code with Online C++ Compiler
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.
Implementation of array using Min heap
C++
#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;
}
You can also try this code with Online C++ Compiler
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.
Implementation of array using Max heap
C++
#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;
}
You can also try this code with Online C++ Compiler
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.
Implementation of array using Quickselect
C++
#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;
}
You can also try this code with Online C++ Compiler
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.
See more, euclid gcd algorithm
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.
Conclusion
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.
Recommended problems -
Do check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.
Refer to our guided paths to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.
24+ registered 
