LeetCode 215 Kth Largest Element in an Array - Example and Complexity Analysis

Trace [3, 2, 1, 5, 6, 4] with k = 2.

Process 3: heap = [3].

Process 2: heap = [2, 3]. Size is k=2.

Process 1: 1 < 2 (heap min). Skip.

Process 5: 5 > 2. Remove 2, add 5. Heap = [3, 5].

Process 6: 6 > 3. Remove 3, add 6. Heap = [5, 6].

Process 4: 4 < 5. Skip.

Heap minimum = 5. That's the 2nd largest.

Process each of $n$ elements with $O(\log k)$ heap operations. Total: $O(n \log k)$ time. Heap size: $O(k)$ space.