LeetCode 703 Kth Largest Element in a Stream - Example and Complexity Analysis

Trace k = 3, initial nums = [4, 5, 8, 2].

Build heap with 3 largest: [4, 5, 8]. Min-heap: top is 4.

add(3): 3 < 4 (heap min), don't add. Return 4.

add(5): 5 > 4, remove 4, add 5. Heap: [5, 5, 8]. Return 5.

add(10): 10 > 5, remove 5, add 10. Heap: [5, 8, 10]. Return 5.

add(9): 9 > 5, remove 5, add 9. Heap: [8, 9, 10]. Return 8.

add(4): 4 < 8 (heap min), don't add. Return 8.

Each add operation: $O(\log k)$ for heap operations. Initialization: $O(n \log k)$. Heap size is always k, so $O(k)$ space.