Heap: Given an array, find the kth largest element in the array

Problem Statement:

You are given an array and a value k.

Then yoou need to return the k th largest elements.

Example:

Input: arr = [1, 2, 3, 4, 5] k = 3
Output: [3, 4, 5]

Solution Explanation:

Solution is very simple.

Use a min heap.

insert the first k elements and then compare the top element with the current element.

If the element is greater than the element then remove the top element and then heapify the heap.

Then insert the element into the vector to store the result.

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

Code Solution

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

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

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

    for (int i = k; i < arr.size(); i++) 
    {

      	if(pq.top() < arr[i]) 
      	{
         	pq.pop();
          	pq.push(arr[i]);
        }
    }

    vector<int> res;
  
    while (!pq.empty()) 
    {
        res.push_back(pq.top());
        pq.pop();
    }
  	
   	return res;
}

int main() 
{
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8};
    vector<int> result = solution(arr, 3);

  	for(int i : result)
      	cout << i << " ";

    return 0;
}

Output

6 7 8