703. Kth Largest Element in a Stream
Model: qwen2.5-coder:14b
Topics: Heap,Design
FAANG asked: 1
Acceptance rate: 50.9%
Problem Breakdown
The problem requires designing a class KthLargest that can efficiently find the k-th largest element in a stream of integers. The class should support two operations:
- Initialization with an integer
kand an initial list of integersnums. - Adding a new integer to the stream and returning the current k-th largest element.
Inputs:
k: An integer representing the position of the largest element to find.nums: A list of integers representing the initial stream.val: An integer to be added to the stream.
Outputs:
- The k-th largest element in the stream after each addition.
Implicit Constraints and Edge Cases:
- The stream can grow dynamically with multiple additions.
- The value of
kis always valid (1 <= k <= 10^4). - The initial list
numsmay be empty, but there will always be at leastkelements when searching for the k-th largest element. - Duplicates are allowed in the stream.
Intuition
A brute-force approach would involve sorting the entire list after each addition and then accessing the k-th largest element. However, this approach is inefficient with a time complexity of O(n log n) per addition, where n is the number of elements in the stream.
The key insight is to maintain a data structure that efficiently keeps track of the k largest elements seen so far. A min-heap (priority queue) is ideal for this purpose because it allows us to keep only the k largest elements and quickly access the smallest among them, which is the k-th largest element in the stream.
Approach
-
Initialization (
__init__method):- Use a min-heap to store the k largest elements.
- Iterate through the initial list
nums. - For each number, add it to the heap.
- If the heap size exceeds k, remove the smallest element (the root of the heap). This ensures that the heap always contains exactly k elements.
-
Adding a new value (
addmethod):- Add the new value to the heap.
- If the heap size exceeds k, remove the smallest element.
- Return the root of the heap, which is the k-th largest element.
Data Structure Choice:
- A min-heap (priority queue) is used because it allows efficient insertion and removal operations while keeping track of the smallest element in constant time.
Complexity Analysis
-
Time Complexity:
- Initialization: O(n log k), where n is the length of
nums. Each insertion into the heap takes O(log k). - Adding a new value: O(log k). Insertion and potential removal from the heap both take O(log k).
- Initialization: O(n log k), where n is the length of
-
Space Complexity:
- O(k). The heap stores at most k elements.
Solution
import heapq
class KthLargest:
def __init__(self, k: int, nums):
self.k = k
self.min_heap = []
for num in nums:
heapq.heappush(self.min_heap, num)
if len(self.min_heap) > k:
heapq.heappop(self.min_heap)
def add(self, val: int) -> int:
heapq.heappush(self.min_heap, val)
if len(self.min_heap) > self.k:
heapq.heappop(self.min_heap)
return self.min_heap[0]
Edge Cases Handled
- Empty Initial List: If
numsis empty, the heap remains empty until at least k elements are added. - Duplicates: The heap can contain duplicates, which is handled naturally by the min-heap operations.
- Negative Numbers: The solution works with negative numbers as well, since the heap operations do not depend on the sign of the numbers.