Kth largest element in an array

July 02, 2022 · 1 min read

https://practice.geeksforgeeks.org/problems/k-largest-elements4206/1

Make heap of size k, then insert remaining only if greater Minheap for k largest, maxheap for k smallest

class Solution {
public:
  vector<int> kLargest(int arr[], int n, int k) {
    priority_queue<int, vector<int>, greater<int>> pq(arr, arr + k);

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

    while (!pq.empty()) {
      res.push_back(pq.top());
      pq.pop();
    }

    reverse(res.begin(), res.end());

    return res;
  }
};