Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Find Median from Data Stream
Bookmark
Sort
Two Heaps
Buckets
Input
Example 1
Example 2
Example 3
Custom
numbers
=
[1, 2, 3]
stream:
data (sorted on each query)
1
2
3
keep two balanced halves, the median sits at the boundary
max-heap
keeps the lower half,
min-heap
the upper half
stream:
data (sorted on each query)
1
2
3
keep two balanced halves, the median sits at the boundary
max-heap
keeps the lower half,
min-heap
the upper half
stream:
data (sorted on each query)
medians:
1
2
3
lower half empty →
1
starts the max-heap
stream:
data (sorted on each query)
medians:
1
2
3
stream:
data (sorted on each query)
medians:
1
2
3
1
odd count → median = top of lower half =
1
stream:
data (sorted on each query)
medians:
1
2
3
1
stream:
data (sorted on each query)
medians:
1
2
3
1
stream:
data (sorted on each query)
medians:
1
2
3
1
1.5
read num =
3
stream:
data (sorted on each query)
medians:
1
2
3
1
1.5
stream:
data (sorted on each query)
medians:
1
2
3
1
1.5
stream:
data (sorted on each query)
medians:
1
2
3
1
1.5
2
final median = 2 after 3 numbers
algo
master
.
io
Step:
Start with an empty list
0 / 22
Input
Example 1
Example 2
Example 3
Custom
numbers
=
[1, 2, 3]
0 / 22
algo
master
.
io
Step:
Start with an empty list
