703. Kth Largest Element In a Stream - Explanation
Description
Design a class to find the kth largest integer in a stream of values, including duplicates. E.g. the 2nd largest from [1, 2, 3, 3] is 3. The stream is not necessarily sorted.
Implement the following methods:
constructor(int k, int[] nums)Initializes the object given an integerkand the stream of integersnums.int add(int val)Adds the integervalto the stream and returns thekthlargest integer in the stream.
Example 1:
Input:
["KthLargest", [3, [1, 2, 3, 3]], "add", [3], "add", [5], "add", [6], "add", [7], "add", [8]]
Output:
[null, 3, 3, 3, 5, 6]
Explanation:
KthLargest kthLargest = new KthLargest(3, [1, 2, 3, 3]);
kthLargest.add(3); // return 3
kthLargest.add(5); // return 3
kthLargest.add(6); // return 3
kthLargest.add(7); // return 5
kthLargest.add(8); // return 6Constraints:
1 <= k <= 10000 <= nums.length <= 1000-1000 <= nums[i] <= 1000-1000 <= val <= 1000- There will always be at least
kintegers in the stream when you search for thekthinteger.
Topics
Recommended Time & Space Complexity
You should aim for a solution with O(nlog(k + 1)) initialization time, O(log(k + 1)) time per add() call, and O(k) space. The total time is O((n + m)log(k + 1)), where n is the initial array length, m is the number of add() calls, and k is the rank of the largest number to track. These bounds assume the heap is trimmed during initialization as described in Hint 4.
Hint 1
A brute force solution would involve sorting the array in every time a number is added using add(), and then returning the k-th largest element. This would take O(m * nlogn) time, where m is the number of calls to add() and n is the total number of elements added. However, do we really need to track all the elements added, given that we only need the k-th largest element? Maybe you should think of a data structure which can maintain only the top k largest elements.
Hint 2
We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes O(log(k + 1)) time since we are storing at most k elements in it before the insertion. Retrieving the top element (the smallest in the heap) takes O(1) time. How can this be useful for finding the k-th largest element?
Hint 3
The k-th largest element is the smallest element among the top k largest elements. This means we only need to maintain k elements in our Min-Heap to efficiently determine the k-th largest element. Whenever the size of the Min-Heap exceeds k, we remove the smallest element by popping from the heap. How do you implement this?
Hint 4
Start with an empty Min-Heap. Insert each initial value and, after each insertion, remove the smallest element if the heap size exceeds k. This keeps initialization to O(nlog(k + 1)) time and O(k) space. Apply the same insert-and-trim steps for each add() call, then return the heap's smallest element, which is the k-th largest element.
Prerequisites
Before attempting this problem, you should be comfortable with:
- Heap Data Structure - Understanding min-heaps and how they maintain the smallest element at the root
- Priority Queues - Using built-in heap implementations for efficient insertion and extraction
- Sorting Algorithms - Understanding basic sorting as a baseline approach
1. Sorting
Intuition
We want the k-th largest number in a stream of values.
The simplest approach:
Every time a new value comes in, insert it, sort the list, and then pick the element at position len(arr) - k.
Sorting keeps the numbers in increasing order, so the k-th largest element will always sit at the same index.
This method is easy to understand but slow because sorting happens every time add() is called.
Algorithm
Initialization
- Store
k. - Store the initial numbers in an array.
add(val)
- Append
valto the array. - Sort the array.
- Return the element at index
len(arr) - k(the k-th largest).
Time & Space Complexity
- Time complexity:
- Space complexity:
- extra space.
- or space depending on the sorting algorithm.
Where is the number of calls made to and is the current size of the array.
2. Min-Heap
Intuition
To maintain the k-th largest element in a stream of numbers, we do not need to store all values.
Instead, we only need to keep track of the k largest elements seen so far.
A min-heap of size k is perfect for this:
- A min-heap always keeps the smallest value at the top.
- If the heap contains the
klargest elements,
then the smallest among them is exactly the k-th largest overall. - Whenever a new number arrives:
- If we add it and the heap grows beyond
k,
we remove the smallest element - because it cannot be in the topkanymore.
- If we add it and the heap grows beyond
This way, the heap always holds exactly the top k elements, and retrieving the k-th largest is O(1).
Algorithm
Initialization
- Insert all initial numbers into a min-heap.
- If the heap size becomes greater than
k, repeatedly remove the smallest element.- After this, the heap contains exactly
kelements.
- After this, the heap contains exactly
add(value)
- Insert the new value into the min-heap.
- If heap size >
k:- Remove the smallest element (the heap root).
- Return the heap's smallest element (the root), which is now the k-th largest.
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.minHeap, self.k = nums, k
heapq.heapify(self.minHeap)
while len(self.minHeap) > k:
heapq.heappop(self.minHeap)
def add(self, val: int) -> int:
heapq.heappush(self.minHeap, val)
if len(self.minHeap) > self.k:
heapq.heappop(self.minHeap)
return self.minHeap[0]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the number of calls made to .
Common Pitfalls
Using a Max-Heap Instead of Min-Heap
A common mistake is using a max-heap to find the k-th largest element. While it seems intuitive to keep the largest elements at the top, a max-heap would require storing all elements and repeatedly extracting the maximum k times for each query. A min-heap of size k is the correct choice because the root always holds the k-th largest element directly, allowing O(1) retrieval after each insertion.
Forgetting to Maintain Heap Size
When using a min-heap, it is essential to remove the smallest element whenever the heap size exceeds k. Failing to do so means the heap grows unbounded, and the root no longer represents the k-th largest element. Always check and pop after each insertion to keep exactly k elements in the heap.
Sign in to join the discussion