Skip to main content

703. Kth Largest Element in a Stream

easyAsked at Microsoft

Kth Largest Element in a Stream is Microsoft's go-to question for whether you reach for the right data structure when 'streaming' enters the problem. The answer is a min-heap of size k — anything else (sorted list, max-heap) has the wrong asymptotic cost.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure org onsite reports list this as a recurring 20-minute streaming-data design question.
  • Blind (2025-12)— Microsoft new-grad reports include Kth Largest in a Stream with the 'why not sort?' follow-up.

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Implement KthLargest class: KthLargest(int k, int[] nums) initializes the object with the integer k and the stream of integers nums. int add(int val) appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Constraints

  • 1 <= k <= 10^4
  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • -10^4 <= val <= 10^4
  • At most 10^4 calls will be made to add.
  • It is guaranteed that there will be at least k elements in the array when you search for the kth element.

Examples

Example 1

Input
["KthLargest","add","add","add","add","add"]
[[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
Output
[null,4,5,5,8,8]

Explanation: k=3 means 'find the 3rd largest at any time.' After each add the heap top is returned.

Approaches

1. Min-heap of size k (optimal)

Keep a min-heap of the k largest so far. On add: push the new value; if size > k, pop the smallest. Heap top is the kth largest.

Time
O(log k) per add
Space
O(k)
class MinHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  peek() { return this.h[0]; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      const n = this.h.length;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let small = i;
        if (l < n && this.h[l] < this.h[small]) small = l;
        if (r < n && this.h[r] < this.h[small]) small = r;
        if (small === i) break;
        [this.h[i], this.h[small]] = [this.h[small], this.h[i]];
        i = small;
      }
    }
    return top;
  }
}

class KthLargest {
  constructor(k, nums) {
    this.k = k;
    this.heap = new MinHeap();
    for (const n of nums) this.add(n);
  }
  add(val) {
    this.heap.push(val);
    if (this.heap.size() > this.k) this.heap.pop();
    return this.heap.peek();
  }
}

Tradeoff: Each add is O(log k), each query is O(1) (peek). Min-heap of SIZE k is the trick — the smallest of the k largest IS the kth largest. A max-heap of everything would be O(log n) per add and O(k log n) per query, which is worse.

2. Sorted array (rejected)

Maintain a sorted array, insert each add in the right place.

Time
O(n) per add
Space
O(n)
class KthLargest {
  constructor(k, nums) { this.k = k; this.arr = [...nums].sort((a, b) => b - a); }
  add(val) {
    let i = 0;
    while (i < this.arr.length && this.arr[i] > val) i++;
    this.arr.splice(i, 0, val);
    return this.arr[this.k - 1];
  }
}

Tradeoff: O(n) per add because splice shifts. Useful only as the wrong answer you name out loud: 'I could sort, but inserts are O(n). I want O(log k) per add — a heap.'

Microsoft-specific tips

Microsoft is grading whether you instinctively pick min-heap-of-size-k and can EXPLAIN why it works. Say: 'the kth largest is the smallest of the k largest. A min-heap of size k stores exactly those k largest; the heap top is the answer. Adds beyond k pop the smallest, which is the only one definitely not in the top-k.' That paragraph is the entire interview.

Common mistakes

  • Using a MAX-heap of size k — wrong because pop-on-overflow removes the largest, not the smallest.
  • Forgetting to initialize the heap with the constructor's nums array.
  • Maintaining a heap of all elements seen — O(log n) per add when O(log k) is achievable.

Follow-up questions

An interviewer at Microsoft may pivot to one of these next:

  • Top K Frequent Elements (LC 347) — same min-heap-of-size-k trick on frequencies.
  • Find Median from Data Stream (LC 295) — two heaps for streaming median.
  • Kth Largest Element in an Array (LC 215) — same problem, single query, allows quickselect.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why min-heap and not max-heap?

Min-heap-of-size-k stores the k largest. The smallest of those — the heap top — IS the kth largest. A max-heap would put the largest at top, which is the 1st largest, not the kth.

What if k > stream length?

The problem guarantees this never happens during add calls; the constructor's nums always has at least k elements eventually.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Kth Largest Element in a Stream and other Microsoft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →