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.
Using a min-heap of size k can efficiently keep track of the kth largest element. This approach relies on the property of a heap where the smallest element (the root) in a min-heap can be accessed in constant time.
Steps:
This implementation uses Python's heapq to manage a min-heap. The initial list of numbers is added to the heap, and then for each additional number, we determine whether it should replace the root of the heap, maintaining the heap size of k.
When a new value is added, if the heap is already full, it only adds the value if it is greater than the current minimum (root), ensuring that at the root is always the kth largest element.
Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.
We maintain a priority queue (min heap) minQ.
Initially, we add the elements of the array nums to minQ one by one, ensuring that the size of minQ does not exceed k. The time complexity is O(n times log k).
Each time a new element is added, if the size of minQ exceeds k, we pop the top element of the heap to ensure that the size of minQ is k. The time complexity is O(log k).
In this way, the elements in minQ are the largest k elements in the array nums, and the top element of the heap is the k^{th} largest element.
The space complexity is O(k).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Min-Heap Approach | Time Complexity: O(n log k) for initialization and O(log k) per add operation. |
| Priority Queue (Min Heap) | — |
| 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 |
Kth Largest Element in a Stream - Leetcode 703 - Python • NeetCode • 215,267 views views
Watch 9 more video solutions →Practice Kth Largest Element in a Stream with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor