Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Sliding Window Median
Bookmark
Input
Example 1
Example 2
Small k=2
Custom
nums
=
[1, 3, -1, -3, 5, 3, 6, 7]
,
k
=
3
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
keep each window split into two balanced halves, median at the boundary
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
keep each window split into two balanced halves, median at the boundary
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
3
1
-1
hand the
1 largest
to the min-heap → balanced halves
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
3
-1
-3
1
-3
enters → -3 ≤ top -1 →
lower half
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
0
medians:
-1
-3
1
-1
nums[1] = 3
leaves → remove from the
min-heap
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
1
size =
1
medians:
-3
5
1
-1
-1
nums[2] = -1
leaves → remove from the
max-heap
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
-3
5
3
1
-1
-1
upper half bigger → move top
3
across
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
1
size =
2
medians:
5
3
6
1
-1
-1
3
6
enters → 6 > top 3 →
upper half
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
5
3
6
1
-1
-1
3
5
odd k → median = top of lower half =
5
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
3
6
7
1
-1
-1
3
5
upper half bigger → move top
6
across
nums:
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
3
6
7
1
-1
-1
3
5
6
medians = [1, -1, -1, 3, 5, 6]
algo
master
.
io
Step:
Start: slide a window of k = 3 over nums, tracking each window's median
0 / 22
Input
Example 1
Example 2
Small k=2
Custom
nums
=
[1, 3, -1, -3, 5, 3, 6, 7]
,
k
=
3
0 / 22
algo
master
.
io
Step:
Start: slide a window of k = 3 over nums, tracking each window's median
