🌱 Keegan's Digital Garden

703. Kth Largest Element in a Stream

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- naive approach would be to sort the list upon each operation
- can use a min heap / priority queue to maintain the order of elements as we add new values

🤔What Did I Struggle With?

💡 Explanation of Solution

- maintain a priority queue of size k
- during initialization , we iterate through the given list and add elements to the heap using the `add` function
- if the heap exceeds size k, remove the smallest element to ensure only the k largest elements are kept
- when a new value is added:
	- push it into the min-heap
	- if the heap size exceeds k, remove the smallest element
	- the kth largest element will always be at the top of the heap

⌛ Complexity Analysis

Time Complexity: O(n log k)

Space Complexity: O(k)

💻 Implementation of Solution

#include <queue>
#include <vector>
using namespace std;
 
class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> minHeap; // Min-heap to store the k largest elements
    int k;
 
public:
    // Initialize with k and a list of numbers
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (int num : nums) {
            add(num); // Use add to build the heap while maintaining size k
        }
    }
    
    // Add a new value and return the kth largest
    int add(int val) {
        minHeap.push(val); // Add the new value to the heap
        if (minHeap.size() > k) {
            minHeap.pop(); // Keep only the k largest elements in the heap
        }
        return minHeap.top(); // The top of the heap is the kth largest element
    }
};
 
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

Graph View