Skip to main content
Talentd

Kth Largest Element in a Stream - Solution & Explanation

EasyTreeDesignBinary Search TreeHeap (Priority Queue)15 min readAsked at: Amazon, Microsoft, Wells Fargo +8
Practice this problem

Problem Statement

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.

Implement the KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
  • int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.

 

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

Example 2:

Input:
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

Output: [null, 7, 7, 7, 8]

Explanation:

KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // return 7
kthLargest.add(10); // return 7
kthLargest.add(9); // return 7
kthLargest.add(9); // return 8

 

Constraints:

  • 0 <= nums.length <= 104
  • 1 <= k <= nums.length + 1
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.

Approach Overview

Problem Overview: You need to design a class that continuously processes numbers from a data stream and returns the kth largest element after each insertion. The stream grows over time, so recomputing the answer from scratch after every new number quickly becomes too slow.

Approach 1: Re-sort the Stream (O(n log n) per insertion)

The most straightforward idea is to keep all elements in a list. Every time a new value arrives, append it and sort the entire collection again. After sorting in descending order, the element at index k-1 is the answer. This approach works for small inputs but becomes inefficient because sorting happens after every insertion. Time complexity is O(n log n) per update and space complexity is O(n). It demonstrates the core idea but does not scale well for continuous streams.

Approach 2: Binary Search Tree (O(log n) average)

You can maintain all elements inside a binary search tree. Each insertion takes O(log n) on average if the tree remains balanced. To retrieve the kth largest element, traverse the tree in reverse in-order (right → root → left). With additional bookkeeping such as subtree sizes, you can directly locate the kth largest node in O(log n). Space complexity remains O(n). While theoretically efficient, implementing a balanced tree or augmented BST adds complexity compared to heap-based solutions.

Approach 3: Min-Heap of Size k (O(log k))

The optimal strategy keeps only the k largest elements seen so far using a heap (priority queue). Specifically, maintain a min-heap of size k. The smallest element in the heap represents the current kth largest value. When a new number arrives, push it into the heap. If the heap size exceeds k, remove the smallest element. This guarantees the heap always stores the top k values from the data stream. Each insertion costs O(log k) time and the heap uses O(k) space.

The key insight: you never need the full sorted stream. Only the largest k values matter. By discarding smaller numbers early, the heap stays small and operations remain fast even as the stream grows to thousands or millions of elements.

Recommended for interviews: The min-heap approach is what interviewers expect. It shows you understand how to maintain order statistics efficiently in a streaming environment. Mentioning the brute-force sorting method demonstrates baseline reasoning, but implementing the O(log k) heap solution shows strong command of priority queues and scalable design.

Approach 1: Min-Heap Approach

Using a min-heap of size k can efficiently keep track of the kth largest element. This approach relies on the property of a heap where the smallest element (the root) in a min-heap can be accessed in constant time.

Steps:

  1. Initialize a min-heap with the first k elements from the array, if available.
  2. For each new element added, check if it's greater than the smallest (the root of the min-heap). If it is, replace the root with this new element and re-heapify.
  3. The root of the min-heap will always be the kth largest element.

This implementation uses Python's heapq to manage a min-heap. The initial list of numbers is added to the heap, and then for each additional number, we determine whether it should replace the root of the heap, maintaining the heap size of k.

When a new value is added, if the heap is already full, it only adds the value if it is greater than the current minimum (root), ensuring that at the root is always the kth largest element.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.

Try this approach in the editor →

Approach 2: Priority Queue (Min Heap)

We maintain a priority queue (min heap) minQ.

Initially, we add the elements of the array nums to minQ one by one, ensuring that the size of minQ does not exceed k. The time complexity is O(n times log k).

Each time a new element is added, if the size of minQ exceeds k, we pop the top element of the heap to ensure that the size of minQ is k. The time complexity is O(log k).

In this way, the elements in minQ are the largest k elements in the array nums, and the top element of the heap is the k^{th} largest element.

The space complexity is O(k).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Min-Heap Approach

Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.

Priority Queue (Min Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Re-sort Entire ArrayO(n log n) per insertionO(n)Simple baseline approach or very small streams
Binary Search TreeO(log n) average insertionO(n)When using ordered trees with subtree counts
Min-Heap of Size kO(log k) per insertionO(k)Best for continuous data streams and interview solutions

Video Solution

Kth Largest Element in a Stream - Leetcode 703 - Python • NeetCode • 226,998 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Largest Element in a Stream easy or hard?
LeetCode classifies this problem as Easy because the core idea is straightforward once you know how heaps work. The challenge mainly comes from recognizing that a fixed-size min-heap efficiently tracks the kth largest element in a continuously growing stream.
Kth Largest Element in a Stream Python/Java solution
Most implementations use the built-in priority queue structures. Python uses heapq, Java uses PriorityQueue, and C++ uses priority_queue with a min-heap configuration. Each insertion pushes the value into the heap and removes the smallest element if the heap size exceeds k.
How to solve Kth Largest Element in a Stream in O(n)?
The streaming version is typically solved with O(log k) per insertion using a min-heap. If you process n insertions, the total runtime becomes O(n log k). This is significantly faster than repeatedly sorting the full list, which would cost O(n log n) per update.
What is the best approach for Kth Largest Element in a Stream?
The most efficient approach uses a min-heap (priority queue) of size k. The heap stores the k largest elements seen so far, and the smallest element in the heap represents the kth largest value. Each insertion takes O(log k) time and the space complexity is O(k). This method avoids sorting the entire stream after every update.
Is Kth Largest Element in a Stream asked at Google/Amazon/Meta?
Kth largest element problems and streaming heap questions frequently appear in interviews at companies like Amazon, Google, and Meta. They test knowledge of heaps, priority queues, and maintaining order statistics in real-time data streams.
What data structure is used in Kth Largest Element in a Stream?
A min-heap (priority queue) is the primary data structure used in the optimal solution. It efficiently maintains the k largest elements while discarding smaller ones. Binary search trees can also solve the problem but are more complex to implement.
What is the time complexity of Kth Largest Element in a Stream?
Using the optimal min-heap approach, each insertion into the stream takes O(log k) time because the heap size never exceeds k. Retrieving the kth largest element is O(1) since it is always the root of the heap. The total space complexity is O(k).

Ready to solve this problem?

Practice Kth Largest Element in a Stream with our built-in code editor and test cases.

Practice on FleetCode
Previous

Finding MK Average

Next

Kth Largest Element in an Array