LeetCode Solutions Blog

Kth Largest Element in a Stream

Number: 789

Difficulty: Easy

Paid? No

Problem Description

We need to implement a class KthLargest that maintains a stream of test scores and returns the kth largest score after each new submission. The kth largest element is defined as the kth highest score in the sorted order of all scores seen so far.

Key Insights

Use a min-heap (priority queue) of fixed size k.
The heap always contains the k largest elements; the smallest element in the heap is the kth largest overall.
When a new test score is added:
- If the heap has less than k elements, simply add the score.
- If the heap is full and the new score is greater than the smallest (heap root), replace the root.
Each add operation runs in O(log k) time.

Space and Time Complexity

Time Complexity: O(log k) per add operation, O(n log k) to build the initial heap. Space Complexity: O(k) for maintaining the heap.

Solution

We use a min-heap to track the k largest numbers. When initializing, we add numbers from the given list to the heap, ensuring not to exceed a size of k. For each add operation, if the new number is greater than the heap minimum, we replace the minimum. The kth largest number is always accessible as the minimum element in the heap.

Code Solutions

import heapq

class KthLargest:
    def __init__(self, k, nums):
        # Save kth value and initialize the min-heap.
        self.k = k
        self.min_heap = nums
        heapq.heapify(self.min_heap)
        # Reduce the heap size to exactly k elements.
        while len(self.min_heap) > k:
            heapq.heappop(self.min_heap)
    
    def add(self, val):
        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, val)
        elif val > self.min_heap[0]:
            heapq.heapreplace(self.min_heap, val)
        # The kth largest element is at the heap root.
        return self.min_heap[0]

# Example usage:
# kthLargest = KthLargest(3, [4, 5, 8, 2])
# print(kthLargest.add(3))   # returns 4
# print(kthLargest.add(5))   # returns 5
# print(kthLargest.add(10))  # returns 5
# print(kthLargest.add(9))   # returns 8
# print(kthLargest.add(4))   # returns 8