Abstract / Summary

Design a class to add integers to a data stream and find the kth largest element at any time.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (1+ million submissions).

Typical patterns to solve this problem:

• Data Stream
• Design
• Heap (Priority Queue)

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class that maintains the k-th largest element of a dynamic integer collection. It leverages Python’s built-in heap utilities to keep a min-heap whose size never exceeds k. The smallest element in this heap is always the current k-th largest value, which can be returned in constant time after each insertion.

Key Steps

Initialization

def __init__(self, k: int, nums: List[int]):
    self.k = k
    self.heap = nums.copy()
    heapify(self.heap)
    while len(self.heap) > k:
        heappop(self.heap)

The constructor stores the target rank k and creates a private copy of the input list. By calling heapify the list is transformed into a valid min-heap in a single linear pass. The subsequent loop repeatedly removes the smallest element until the heap size matches k. After this process the heap contains exactly the k largest values from the original collection, and its root (self.heap[0]) is the k-th largest.

Adding a Value

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

When a new integer arrives, it is inserted into the heap with heappush. If the insertion makes the heap larger than k, the smallest element is removed with heappop. This guarantees that the heap never stores more than k items, and the root remains the current k-th largest. The method returns this root directly.

Edge Cases Handled

The code gracefully deals with an empty initial list. heapify on an empty list produces an empty heap, and the trimming loop does not execute because the length is already zero. Subsequent calls to add will populate the heap up to size k without any special-case logic.

When k equals one, the heap is reduced to a single element after initialization. Each call to add pushes the new value and immediately discards the smaller of the two, leaving the maximum value at the root. This behavior correctly yields the largest element at all times.

If the initial list contains fewer than k elements, the trimming loop never runs, leaving the heap size equal to the number of supplied values. The add method then grows the heap until it reaches k, after which the size-capping logic activates. Thus the class works for any relationship between the size of nums and the requested rank k.

Performance Optimizations

The use of heapify is a primary optimization. By converting the entire input list into a heap in one operation, the constructor avoids the overhead of inserting each element individually, which would require repeated rebalancing. This approach reduces the work needed to establish the initial heap structure.

Maintaining the heap at a fixed size of k eliminates unnecessary growth. Each insertion is followed by at most one removal, ensuring that the heap never exceeds k+1 elements. This bounded size keeps the internal heap operations cheap, as the cost of heappush and heappop depends on the current heap height, which is limited by k.

The decision to store only the k largest values means that memory consumption is directly proportional to k, regardless of how many values are added over the lifetime of the object. This selective retention avoids the linear growth that a naïve approach of storing all elements would incur.

By returning the root of the heap (self.heap[0]) after each addition, the implementation provides immediate access to the result without additional traversal or computation. This direct retrieval leverages the heap property that the smallest element is always at index zero.

Imagine a magical toy bucket that only likes to keep track of a few of the biggest blocks. The code starts by setting a special number called k, which tells the bucket how many big blocks to hold onto. If the bucket has too many blocks inside, it does a little cleaning and tosses out the smallest ones until it matches the number k.

When a brand new block arrives, the bucket welcomes it inside. After adding the new block, the bucket checks to see if it has become too crowded again. If the bucket is suddenly holding more blocks than its limit, it quickly finds the smallest block currently sitting inside and lets it go. This keeps the bucket perfectly filled with only the absolute largest blocks that have been put in so far. The very smallest block among those champions is always waiting right at the very front for whenever someone wants to peek at it.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python		JS			Go		TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy				C#
	black-shadows	C++
	bujosa			Python
	charles-wangkai		Java
	Dijkstra-Edu		Java
	everthis					JS
	fartem							Ruby
	FelixFan1122		Java
	fpdjsns	C++
	halfrost								Go
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007			Python
	qiyuangong		Java
	ruoru						Rust
	Shamik07									Dart
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28		Java
	withaarzoo	C++
	YuriSpiridonov			Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality