Arrays: Find the k’th smallest/largest element in an array

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

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *