703. Kth Largest Element in a Stream

EasyView on LeetCode

Tree Design Binary Search Tree Binary Tree Heap (Priority Queue)

Intuition

Maintain a min-heap of size k. The kth largest is always the heap minimum.

Algorithm

1Constructor: add all initial elements, keeping heap size ≤ k.
2Add(val): push val. If heap size > k, pop minimum. Return heap top.

Common Pitfalls

•Initialize by adding all elements and trimming to k, not just inserting first k.

703.cs

// Approach: Min-heap of size k — the top is always the k-th largest;
// add each new element and evict the minimum if size exceeds k.
// Time: O(n log k) build, O(log k) add Space: O(k)

public class KthLargest
{
    private int k;
    private PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
    public KthLargest(int k, int[] nums)
    {
        this.k = k;
        foreach (int num in nums)
            Heapify(num);
    }

    private void Heapify(int num)
    {
        pq.Enqueue(num, num);
        if (pq.Count > k)
            pq.Dequeue();
    }

    public int Add(int val)
    {
        Heapify(val);
        return pq.Peek();
    }
}

Was this solution helpful?