Heap: Given an array and a value K, return the kth smallest element

Problem Statement:

Given an array and a value K, return the kth smallest element

Example:

Input: arr = [3, 6, 1, 2, 7, 8] k = 2

Output: 2

Explanation: 2 is the second smallest element

Solution 1: Naive Approach

Sort the array and then return the kth element.

Time Complexity: O(n log(n))
Space Complexity: O(1)

Solution 2: Heaps Approach

We will create Max heap for the first k element.

For the rest of the element, if the element is smaller than the top of the heap, pop an element from heap and insert into the heap.

Why are we using Max Heap ?

Here when ever we get smaller element we pop the top element from the heap (the largest element) and insert the smaller element.

Now when we do not have any more element, by default, the top element of the heap will have the kth smallest element.

Time Complexity: O(n * log(k))
Space Complexity: O(1)

Code Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int solution_2 (vector<int>& arr, int k) 
{
    
    priority_queue<int> pq;

    for (int i = 0; i < k; i++)
    {
        pq.push(arr[i]);
    }

    for (int i = k; i < arr.size(); i++)
    {
    	if(arr[i] < pq.top())
    	{
    		pq.pop();
        	pq.push(arr[i]);
       	}
    }    

    return pq.top();
}


int solution_1 (vector<int>& arr, int k)
{
    sort(arr.begin(), arr.end());

    return arr[k - 1];
}

int main()
{
    vector<int> arr = {3, 6, 1, 2, 7, 8};
    int k = 2;

    cout << solution_1(arr, k)<<endl;
    cout << solution_2(arr, k);
}

Output

2
2