#703

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Kth Largest Element in a Stream

Find the kth largest element in a dynamic stream using binary-tree traversal and efficient state tracking with a min-heap.

tree design binary search tree heap priority queue binary tree

Problem Statement

You are designing a system for a university admissions office that continuously monitors applicants' test scores. The goal is to always identify the kth highest score among all submitted results to help make dynamic admission decisions as new scores arrive.

Implement the KthLargest class to maintain a stream of integers, supporting real-time additions and returning the kth largest score after each insertion. Your class should be able to initialize with an integer k and an initial array of scores, then efficiently update the kth largest value whenever a new score is added.

Examples

Example 1

Input: ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

Example 2

Input: ["KthLargest", "add", "add", "add", "add"] [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

Output: [null, 7, 7, 7, 8]

Constraints

0 <= nums.length <= 104
1 <= k <= nums.length + 1
-104 <= nums[i] <= 104
-104 <= val <= 104
At most 104 calls will be made to add.

Solution Approach

Use a Min-Heap for State Tracking

Maintain a min-heap of size k to store the current k largest elements. The top of the heap always represents the kth largest score. When a new value is added, push it to the heap and remove the smallest element if the heap exceeds size k, keeping the heap size constant.

Initialization with Existing Stream

During initialization, iterate through the given array of numbers and push each into the min-heap while maintaining its size at k. This ensures that before any add operation, the heap correctly represents the current k largest elements in the stream.

Handle Real-Time Additions Efficiently

For each add operation, push the new score into the heap. If the heap size exceeds k, pop the smallest element. Return the top of the heap as the current kth largest value. This guarantees O(log k) time per insertion and correct kth largest tracking at all times.

Complexity Analysis

Metric	Value
Time	O((M + N) \cdot \log k)
Space	O(k)

Time complexity is O((M + N) * log k) where N is initial array length and M is number of add calls; each insertion into a size-k min-heap takes O(log k). Space complexity is O(k) to store the min-heap representing the k largest elements.

What Interviewers Usually Probe

Ask about handling large dynamic streams and maintaining a fixed-size tracking structure.
Check if the candidate correctly initializes the heap and updates it with each add operation.
Probe knowledge of edge cases, such as when the initial array has fewer than k elements.

Common Pitfalls or Variants

Common pitfalls

Using a full sorted array each time, leading to O(N log N) insertion time per add.
Forgetting to maintain the heap size at exactly k, causing incorrect kth largest results.
Not handling duplicate values correctly, which may affect the min-heap top.

Follow-up variants

Track the kth smallest element in a live data stream instead of the largest.
Support a stream of real numbers or floats instead of integers with the same heap approach.
Allow dynamic updates to k during the stream, requiring heap reconstruction or resizing.

FAQ

What is the most efficient data structure to maintain the kth largest element in a stream?

A min-heap of size k efficiently maintains the kth largest element, ensuring O(log k) insertion and O(1) retrieval.

How does the KthLargest class handle initialization with an existing array?

It iterates through the initial array, inserting each element into the min-heap while maintaining a size of k, ensuring the kth largest element is correct from the start.

What should be returned after each add operation?

After adding a new number, return the top of the min-heap, which represents the current kth largest element in the stream.

Can duplicates affect the kth largest result?

Yes, duplicates should be correctly inserted into the min-heap since the kth largest depends on the exact multiset of values.

How does binary-tree traversal relate to this problem?

The pattern of maintaining a min-heap mirrors binary-tree traversal logic, where we track and update hierarchical state to efficiently find the kth largest element.

terminal

Solution

Solution 1: Priority Queue (Min Heap)

We maintain a priority queue (min heap) $\textit{minQ}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_q = []
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heappush(self.min_q, val)
        if len(self.min_q) > self.k:
            heappop(self.min_q)
        return self.min_q[0]


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

Continue Practicing

#449 serialize and deserialize bst #173 binary search tree iterator #669 trim a binary search tree