Skip to main content

703. Kth Largest Element in a Stream

easy

Design a class that returns the kth largest element from a stream as new numbers are added. The canonical fixed-size min-heap problem — and a common warm-up before sliding-window-median.

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

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: KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4. kthLargest.add(5); // return 5. kthLargest.add(10); // return 5. kthLargest.add(9); // return 8. kthLargest.add(4); // return 8.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Re-sorting on every add is O(n log n) per call — too slow under the constraints.

Hint 2

You only ever care about the top k elements. Anything smaller than the kth largest is dead weight.

Hint 3

Keep a min-heap of size k. The root is the kth largest by definition.

Hint 4

On add: push the new value. If heap size exceeds k, pop. Return the root.

Solution approach

Reveal approach

Maintain a fixed-size min-heap of size k. The smallest element in this heap (the root) is always the kth largest element seen so far, because k-1 larger elements live above it in the heap. On add(val): push val into the heap; if size exceeds k, pop the smallest. Then return the root. Constructor seeds the heap by iterating nums and applying the same add logic. add is O(log k), the constructor is O(n log k) where n = nums.length. Space is O(k). The min-heap of size k is the canonical fixed-size heap pattern — same shape applies to top-k-frequent-elements and k-closest-points.

Complexity

Time
O(log k) per add, O(n log k) constructor
Space
O(k)

Related patterns

  • heap
  • top-k-elements
  • design
  • data-stream

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Kth Largest Element in a Stream and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →