loading

Kth Largest Element in a Stream — Step-by-Step Visualization

easyLeetCode #703TreeDesignBinary Search TreeHeap (Priority Queue)Binary TreeData Stream

Design a class to find the `k-th` largest element in a stream. Note that it is the `k-th` largest element in the sorted order, not the `k-th` distinct element. Implement `KthLargest` class: `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`. `int add(int val)` Appends the integer `val` to the stream and returns the element representing the `k-th` largest element in the stream.

Algorithm Pattern

Min-Heap of size K

Key Idea

To find the Kth largest element in a dynamic stream, we can use a min-priority queue (min-heap) to store only the `K` largest elements seen so far. In a min-heap of size `K`, the smallest element (at the root) is the Kth largest element of the entire stream. When a new element comes in, we add it to the heap and immediately remove the smallest element if the heap size exceeds `K`.

Step-by-Step Approach

  1. Initialize a min-heap with the given `nums`.
  2. Pop elements from the min-heap until its size is at most `k`.
  3. For each new element `add(val)`:
  4. Push `val` onto the min-heap.
  5. If `len(heap) > k`, pop the smallest element.
  6. The root of the heap is the current Kth largest element.

Common Gotchas

  • It is the Kth *largest*, which is why we use a *min*-heap of size K.
  • Initially, if the array has fewer than K elements, we just keep adding.

Related Problems

← All problems