💬 Discord
Sign In
NeetCode #523LC-703EasyHeap / Priority QueueNC 150NC 250
← Back to All Problems

#523 · #703 · Kth Largest Element in a Stream(数据流中的第 K 大元素)

📌 Problem Statement & Constraints

Design a class that finds the k-th largest element in a stream. KthLargest(k, nums) initialises with the initial numbers, and add(val) appends a value and returns the k-th largest so far. Constraints: 1 <= k <= 10^4; at most 10^4 calls to add.

💡 Core Algorithmic Approaches

  1. Keep a min-heap of size k holding the k largest values seen so far.
  2. The heap's root is then the k-th largest.
  3. On add, push the value and pop the smallest if the size exceeds k.
  4. The initialisation must also trim the heap to size k.

💻 Benchmark Python3 Implementation

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        import heapq
        self.k = k
        self.heap = nums[:]
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)       # keep only the k largest

    def add(self, val: int) -> int:
        import heapq
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]                # the k-th largest is the heap root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log k) for the initialisation and O(log k) per add.
💾 Space Complexity
O(k) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Using a max-heap of everything: the k-th largest would require popping k times per query.
  • Forgetting to trim the heap in the constructor: the root would not be the k-th largest until enough values were added.
  • Using a sorted list and inserting: O(n) per insertion due to shifting.
  • Returning heap[0] before trimming: the answer would be wrong while the heap is oversized.