Watch 10 video solutions for Kth Largest Element in a Stream, a easy level problem involving Tree, Design, Binary Search Tree. This walkthrough by NeetCode has 215,267 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.
You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.
Implement the KthLargest class:
KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.
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]
Explanation:
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]
Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
Constraints:
0 <= nums.length <= 1041 <= k <= nums.length + 1-104 <= nums[i] <= 104-104 <= val <= 104104 calls will be made to add.Problem Overview: You need to design a class that continuously processes numbers from a data stream and returns the kth largest element after each insertion. The stream grows over time, so recomputing the answer from scratch after every new number quickly becomes too slow.
Approach 1: Re-sort the Stream (O(n log n) per insertion)
The most straightforward idea is to keep all elements in a list. Every time a new value arrives, append it and sort the entire collection again. After sorting in descending order, the element at index k-1 is the answer. This approach works for small inputs but becomes inefficient because sorting happens after every insertion. Time complexity is O(n log n) per update and space complexity is O(n). It demonstrates the core idea but does not scale well for continuous streams.
Approach 2: Binary Search Tree (O(log n) average)
You can maintain all elements inside a binary search tree. Each insertion takes O(log n) on average if the tree remains balanced. To retrieve the kth largest element, traverse the tree in reverse in-order (right → root → left). With additional bookkeeping such as subtree sizes, you can directly locate the kth largest node in O(log n). Space complexity remains O(n). While theoretically efficient, implementing a balanced tree or augmented BST adds complexity compared to heap-based solutions.
Approach 3: Min-Heap of Size k (O(log k))
The optimal strategy keeps only the k largest elements seen so far using a heap (priority queue). Specifically, maintain a min-heap of size k. The smallest element in the heap represents the current kth largest value. When a new number arrives, push it into the heap. If the heap size exceeds k, remove the smallest element. This guarantees the heap always stores the top k values from the data stream. Each insertion costs O(log k) time and the heap uses O(k) space.
The key insight: you never need the full sorted stream. Only the largest k values matter. By discarding smaller numbers early, the heap stays small and operations remain fast even as the stream grows to thousands or millions of elements.
Recommended for interviews: The min-heap approach is what interviewers expect. It shows you understand how to maintain order statistics efficiently in a streaming environment. Mentioning the brute-force sorting method demonstrates baseline reasoning, but implementing the O(log k) heap solution shows strong command of priority queues and scalable design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Re-sort Entire Array | O(n log n) per insertion | O(n) | Simple baseline approach or very small streams |
| Binary Search Tree | O(log n) average insertion | O(n) | When using ordered trees with subtree counts |
| Min-Heap of Size k | O(log k) per insertion | O(k) | Best for continuous data streams and interview solutions |