LeetEye LeetEye
Hard Heap / Priority Queue ~5 min

Kth Largest Element in a Stream

heap kth-largest-element-in-a-stream

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth 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 kth largest element in the stream.

Examples

Example 1
Input: ["KthLargest", "add", "add", "add", "add", "add"]
Output: [null, 4, 5, 5, 8, 8]
Key Insight

Use a min-heap of size k. The root is always the kth largest.

Min-heap of size k: if new element > root, replace root. Root always gives kth largest.

How to Approach This Problem

Pattern Recognition: When you see keywords like kth largest element in a stream heap, think Heap / Priority Queue.

Step-by-Step Reasoning

1 For kth largest, we use min-heap because:
Answer: Root gives us the smallest of the k largest = kth largest
With k elements in min-heap, root is smallest = kth largest overall.
2 We maintain heap of size:
Answer: k
Only keep the k largest. Anything smaller isn't relevant.
3 If new element > heap root and heap has k elements:
Answer: Pop root, push new element
New element should be in top k. Old minimum is no longer in top k.
4 If new element < heap root and heap has k elements:
Answer: Ignore new element
New element isn't in top k. Don't add it.
5 If nums has fewer than k elements initially:
Answer: Push all, wait for more elements
Start with what we have. Add more as they come.
6 The kth largest is:
Answer: Heap root
Min-heap root = smallest in heap = kth largest overall.

Solution

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        
        while len(self.heap) > k:
            heapq.heappop(self.heap)
    
    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        
        return self.heap[0]

Complexity Analysis

Time O(log k) per add
Space O(k)

Master This Pattern

Build intuition with interactive MCQs. Practice Heap / Priority Queue problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye