Question:
Given an unsorted array with distinct elements, you are also given an integer “k”.
You need to find the k’th smallest/largest element in the array.
Example:
Input : {5, 6, 7, 8, 9, 10}
k = 2
k’th smallest element = 6
k’th largest element = 9
Solution:
We can solve this question by different methods. Some of the methods are discussed below:
1. By Sorting
2. By using MAX heap
3. By using MIN heap
4. By using quick-select algorithm [discussed in separate post]
Method 1: By Sorting
This method is very straight forward.
First short the array, then return the kth smallest element in the array.
Here the time complexity is O(nlogn), if you consider merge sort.
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
using namespace std;
int get_kth_smallest(int arr[], int len, int key)
{
sort(arr, arr + len);
return arr[key - 1];
}
int main()
{
int arr[] = {5, 3, 2, 6, 7, 9, 10, 12};
int len = 8;
int key = 2;
cout<<"Original array is = ";
for (int i = 0; i < len; ++i)
{
cout<<arr[i]<< " ";
}
cout<<"\n";
cout<<"\nThe kth smallest element is = "<<get_kth_smallest(arr, len, key);
cout<<endl;
return 0;
}
Output:
Original array is = 5 3 2 6 7 9 10 12
The kth smallest element is = 3
Method 2: By using MAX heap
We follow below steps to find kth smallest element using MAX heap:
1. First construct Max Heap of K elements and insert first “k” elements into the heap arr[0 .. k-1].
2. Then for each remaining elements from the array arr[k .. n-1], check if the element is smaller than the root. If it is smaller, make it as root and call the heapify method, else ignore it.
3. We do the above step till the array elements are exhausted.
4. Finally the root element of Max Heap is the kth smallest element.
Time Complexity by using MAX Heap: O(k + (n-k) log(k))
Let us understand how we arrived at that complexity.
1. To create a heap for the first time for first k elements it will take O(k) time.
2. To heapify k elements it will take O(log(k)) time.
3. We need to insert the remaining (n-k) elements into the heap. For each element inserted, it will take O(log(k)) time to heapify.
4. So total to insert all the (n-k) elements it will take O((n-k) log(k)).
5. So totally it will take O(k + (n-k) log(k)) time
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <queue>
using namespace std;
int get_kth_smallest_using_max_heap(vector<int> &v, int k)
{
// create Max Heap for the first k elements
priority_queue<int, vector<int>> pq(v.begin(), v.begin() + k);
// Check for remaining elements
for (int i = k; i < v.size(); i++)
{
// check if the current element is less than the root
if (v[i] < pq.top())
{
// if it is less then replace it with root
pq.pop();
pq.push(v[i]);
}
}
// return the root of max-heap
return pq.top();
}
int main()
{
vector<int> vec = { 7, 6, 4, 2, 5, 1 };
const size_t k = 2;
cout << "K'th smallest element in the array using Max Heap is " <<
get_kth_smallest_using_max_heap(vec, k);
return 0;
}
Output:
K'th smallest element in the array using Max Heap is 2
Method 3: By using MIN heap
We follow below steps to find kth smallest element using MIN heap:
1. Construct MIN Heap.
2. Then remove the root element k times to get the kth smallest element.
3. For this we can use priority queue from C++ STD lib.
4. We need to use “std::greater” to make priority queue as a Min Heap.
Time Complexity by using MIN Heap: O(n + klog(n))
Let us understand how we arrived at that complexity.
1. To create a heap for the first time it will take O(n) time.
2. To heapify n elements it will take O(log(n)) time.
3. We need to pop/remove “k” elements. For each element removed it will take O(log(n)) time to heapify.
4. So it will take O((k)log(n)).
5. So totally it will take O(n + (k) log(n)) time
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <queue>
using namespace std;
int get_kth_smallest_using_min_heap(vector<int> &v, int k)
{
// create Min Heap
priority_queue<int, std::vector<int>, std::greater<>> pq(v.begin(), v.end());
// pop (k-1) times
while (--k) {
pq.pop();
}
// return the root of min-heap
return pq.top();
}
int main()
{
vector<int> vec = { 7, 6, 4, 2, 5, 1 };
const size_t k = 2;
cout << "K'th smallest element in the array using Min Heap is " <<
get_kth_smallest_using_min_heap(vec, k)<<endl;
return 0;
}
Output:
K'th smallest element in the array using Min Heap is 2