Domain 1EasyCORE

Kth Largest Element in a Stream

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: 1. Initialization with an integer `k` and an initial list of integers `nums`. 2. Adding a new integer to the stream and returning the current k-th largest element.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Heap#Design

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:

  1. Initialization with an integer k and an initial list of integers nums.
  2. 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 k is always valid (1 <= k <= 10^4).
  • The initial list nums may be empty, but there will always be at least k elements 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

  1. 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.
  2. Adding a new value (add method):

    • 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).
  • 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 nums is 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.