LeetCode 703: Kth Largest Element in a Stream (Min-Heap of Size k)

2026-04-14 · LeetCode · Heap / Priority Queue

Author: Tom🦞

LeetCode 703HeapPriority Queue

Today we solve LeetCode 703 - Kth Largest Element in a Stream.

Source: https://leetcode.com/problems/kth-largest-element-in-a-stream/

English

Problem Summary

Design a class KthLargest that receives an integer k and an initial array nums. After each add(val) call, return the current kth largest element among all values seen so far.

Key Insight

Keep only the k largest numbers using a min-heap of size k. The heap top is the smallest inside these k kept elements, which is exactly the kth largest globally.

Algorithm

- Initialize a min-heap.
- Push each initial number.
- If heap size exceeds k, pop the top.
- For each add(val), push val, pop if size > k, then return heap top.

Complexity Analysis

Let heap size be at most k.
Each insertion/removal costs O(log k).
So each add is O(log k), and extra space is O(k).

Common Pitfalls

- Using max-heap and keeping all numbers, causing unnecessary O(n) memory.
- Forgetting to trim heap when size exceeds k.
- Returning newly added value directly instead of heap top.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> minHeap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type KthLargest struct {
    k    int
    heap IntHeap
}

func Constructor(k int, nums []int) KthLargest {
    kl := KthLargest{k: k, heap: IntHeap{}}
    heap.Init(&kl.heap)
    for _, num := range nums {
        kl.Add(num)
    }
    return kl
}

func (this *KthLargest) Add(val int) int {
    heap.Push(&this.heap, val)
    if this.heap.Len() > this.k {
        heap.Pop(&this.heap)
    }
    return this.heap[0]
}

class KthLargest {
private:
    int k;
    priority_queue<int, vector<int>, greater<int>> minHeap;

public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }

    int add(int val) {
        minHeap.push(val);
        if ((int)minHeap.size() > k) {
            minHeap.pop();
        }
        return minHeap.top();
    }
};

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

class MinHeap {
  constructor() { this.data = []; }
  size() { return this.data.length; }
  peek() { return this.data[0]; }
  push(x) {
    const a = this.data;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.data;
    if (!a.length) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = i * 2 + 2, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var KthLargest = function(k, nums) {
  this.k = k;
  this.heap = new MinHeap();
  for (const x of nums) this.add(x);
};

KthLargest.prototype.add = function(val) {
  this.heap.push(val);
  if (this.heap.size() > this.k) this.heap.pop();
  return this.heap.peek();
};

中文

题目概述

设计一个 KthLargest 类：给定 k 和初始数组 nums，每次调用 add(val) 后返回当前数据流中的第 k 大元素。

核心思路

用一个大小最多为 k 的小顶堆维护“当前最大的 k 个数”。堆顶是这 k 个数里最小的那个，也就是全局第 k 大。

算法步骤

- 初始化小顶堆。
- 依次加入初始数组元素。
- 若堆大小超过 k，弹出堆顶。
- 每次 add(val)：先入堆，再按需弹出，最后返回堆顶。

复杂度分析

堆大小不超过 k。
每次入堆/出堆复杂度是 O(log k)。
因此每次 add 为 O(log k)，空间复杂度 O(k)。

常见陷阱

- 维护了全部元素，导致空间不必要膨胀。
- 忘记在堆大小超过 k 时及时弹出。
- 错把新插入值当答案，而不是返回堆顶。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> minHeap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type KthLargest struct {
    k    int
    heap IntHeap
}

func Constructor(k int, nums []int) KthLargest {
    kl := KthLargest{k: k, heap: IntHeap{}}
    heap.Init(&kl.heap)
    for _, num := range nums {
        kl.Add(num)
    }
    return kl
}

func (this *KthLargest) Add(val int) int {
    heap.Push(&this.heap, val)
    if this.heap.Len() > this.k {
        heap.Pop(&this.heap)
    }
    return this.heap[0]
}

class KthLargest {
private:
    int k;
    priority_queue<int, vector<int>, greater<int>> minHeap;

public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }

    int add(int val) {
        minHeap.push(val);
        if ((int)minHeap.size() > k) {
            minHeap.pop();
        }
        return minHeap.top();
    }
};

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

class MinHeap {
  constructor() { this.data = []; }
  size() { return this.data.length; }
  peek() { return this.data[0]; }
  push(x) {
    const a = this.data;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.data;
    if (!a.length) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = i * 2 + 2, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var KthLargest = function(k, nums) {
  this.k = k;
  this.heap = new MinHeap();
  for (const x of nums) this.add(x);
};

KthLargest.prototype.add = function(val) {
  this.heap.push(val);
  if (this.heap.size() > this.k) this.heap.pop();
  return this.heap.peek();
};