Abstract / Summary

Design a data structure that supports adding numbers and finding the current median efficiently.

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 55% (2+ million submissions).

Typical patterns to solve this problem:

• Data Stream
• Design
• Heap (Priority Queue)
• Sorting
• Two Pointers

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 class implements a streaming median calculator. It maintains two priority queues-one acting as a max-heap for the lower half of the numbers and one as a min-heap for the upper half. By keeping the sizes of the two heaps balanced, the median can be derived directly from the top elements of the heaps.

Core Components

Initialization

class MedianFinder:
    def __init__(self):
        self.left  = [] # invert sign to make it a max-heap
        self.right = []

The constructor creates two empty lists that will be managed by the heap interface. The left heap stores the smaller half of the data with inverted signs, turning Python’s min-heap into a max-heap. The right heap stores the larger half in natural order.

Adding a Number

def addNum(self, num: int) -> None:
    if len(self.left) == len(self.right):
        heappush(self.left, -num)
        if not self.right:
            return
    else:
        heappush(self.right, num)

    l = -self.left[0]
    r =  self.right[0]
    if l > r:
        heapreplace(self.left,  -r)
        heapreplace(self.right,  l)

When the two heaps have equal size, the new element is first placed into the left heap with a sign inversion. If the right heap is still empty after this insertion, the method returns early because there is no counterpart to compare against. When the heaps are imbalanced, the element is pushed onto the right heap.

After the insertion, the method extracts the top values of both heaps (l from left and r from right). If the maximum of the lower half exceeds the minimum of the upper half, the two top elements are swapped using heapreplace. This step restores the invariant that every element in left is less than or equal to every element in right.

Finding the Median

def findMedian(self) -> float:
    if len(self.left) > len(self.right):
        return -self.left[0]

    return 0.5 * (-self.left[0] + self.right[0])

If the left heap contains one more element than the right heap, the median is the top of left (converted back to a positive value). Otherwise the heaps are of equal size and the median is the average of the two top elements.

Edge Cases Handled

The implementation gracefully handles the situation where the first number is added: the early return after pushing onto left avoids an attempt to access right[0] when right is still empty. When the total count of numbers is odd, the extra element resides in left, guaranteeing that the median is always the maximum of the lower half without additional calculations. The conditional swap after each insertion ensures that even when a newly added number would violate the ordering between the two halves, the heaps are immediately corrected, preserving the correct median invariant.

Performance Optimizations

Using two heaps provides logarithmic time for each insertion while keeping median retrieval at constant time, because the median is always available at the root of one or both heaps. The sign inversion technique for left eliminates the need for a separate max-heap implementation, allowing the code to reuse Python’s highly optimized heapq module for both halves. The heapreplace operation swaps the root elements in a single heap operation, which is more efficient than a pop-followed-push sequence, reducing the number of heap adjustments required after each insertion.

Imagine having two toy boxes sitting on the floor. One box is for the smaller numbers and the other box is for the bigger numbers. The goal is to keep the number of toys in both boxes almost exactly the same so that the middle of the group is easy to find.

When a new number shows up, the code first looks to see which box needs a toy to keep things balanced. It puts the number into one of the boxes, but it does a little check afterward. It compares the biggest number in the small box to the smallest number in the big box. If it notices that a big number accidentally landed in the small box or a small number ended up in the big box, it swaps them around until everyone is in the right place.

To figure out the middle, the code peeks at the very front of both boxes. If there is an odd number of toys in total, the one extra toy sitting at the front of the small box is the middle ground. If there is an even total, the code takes the front toy from both boxes and blends them together in the middle to find the perfect center point.

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

not analyzed yet

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++	Python	Java										TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	Rust	JS					Go	Swift	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	AdelDaniel										Dart
	aylei					Rust
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis						JS
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	Garvit244		Python
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	martianoff								Scala
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02							C
	vthwang			Java
	wisdompeak	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, Swift, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
Garvit244	Python
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
martianoff	Scala
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
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