Sponsored
Sponsored
Using a min-heap of size k can efficiently keep track of the kth largest element. This approach relies on the property of a heap where the smallest element (the root) in a min-heap can be accessed in constant time.
Steps:
Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.
1#include <queue>
2#include <vector>
3
4class KthLargest {
5 int k;
6 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
7
8public:
9 KthLargest(int k, std::vector<int>& nums) : k(k) {
10 for (int num : nums) {
11 add(num);
12 }
13 }
14
15 int add(int val) {
16 if (minHeap.size() < k) {
17 minHeap.push(val);
18 } else if (val > minHeap.top()) {
19 minHeap.pop();
20 minHeap.push(val);
21 }
22 return minHeap.top();
23 }
24};This C++ solution leverages the priority_queue for its min-heap functionality, controlled by a comparison function. Similar to other implementations, it manages a heap of size k, efficiently discarding the smallest elements when appropriate.