Heap / Priority Queue

LeetCode 703

LeetCode #703Difficulty: EasyNeetCode 150

LeetCode 703: Kth Largest Element in a Stream

LeetCode

Design a class to find the kth largest element in a stream.

Problem Description

Design a class to find the kth largest element in a stream.

Examples:
Input: k=3, nums=[4,5,8,2], add(3)
Output: 4
Constraints:
  • 1 <= k <= 10^4

Core Mental Model

Maintain a Min-Heap of exact size K. The root is always the Kth largest element overall.

Formal Loop Invariant

Invariant: Min-Heap contains the K largest elements seen so far; minimum of these is the Kth largest.

Key Architectural Takeaway:

To track K largest, maintain a Min-Heap; to track K smallest, maintain a Max-Heap.

Asymptotic Complexity Analysis

Time ComplexityO(log K) per insertLinear scan
Space ComplexityO(K)Constant auxiliary

Bottleneck: Heap rebalance takes log K.

Edge Cases & Screener Traps

  • Heap size < K