Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Falling Squares
Bookmark
Brute Force
Segment Tree
Input
Standard
Stacking
Adjacent
Overlapping
Custom
positions
=
[[1,2],[2,3],[6,1]]
drop(1, 2)
=
?
drop(2, 3)
=
?
drop(6, 1)
=
?
1
2
3
4
5
6
7
each square falls at x = left, lands on the tallest stack it overlaps
drop(1, 2)
=
?
drop(2, 3)
=
?
drop(6, 1)
=
?
1
2
3
4
5
6
7
each square falls at x = left, lands on the tallest stack it overlaps
drop(1, 2)
=
?
drop(2, 3)
=
?
drop(6, 1)
=
?
2
1
2
3
4
5
6
7
square 1
: falls over x ∈ [
1
,
3
) · compressed [0..1]
drop(1, 2)
=
?
drop(2, 3)
=
?
drop(6, 1)
=
?
base 0
2
1
2
3
4
5
6
7
top = base + side = 0 + 2 =
2
drop(1, 2)
=
2
drop(2, 3)
=
?
drop(6, 1)
=
?
2
max 2
1
2
3
4
5
6
7
maxHeight = max(0, 2) =
2
· ans = [2]
drop(1, 2)
=
2
drop(2, 3)
=
?
drop(6, 1)
=
?
2
base 2
3
max 2
1
2
3
4
5
6
7
segment tree: tallest stack under it =
base = 2
drop(1, 2)
=
2
drop(2, 3)
=
?
drop(6, 1)
=
?
2
base 2
3
max 2
1
2
3
4
5
6
7
top = base + side = 2 + 3 =
5
drop(1, 2)
=
2
drop(2, 3)
=
5
drop(6, 1)
=
?
2
3
max 5
1
2
3
4
5
6
7
maxHeight = max(2, 5) =
5
· ans = [2, 5]
drop(1, 2)
=
2
drop(2, 3)
=
5
drop(6, 1)
=
?
2
3
base 0
1
max 5
1
2
3
4
5
6
7
segment tree: tallest stack under it =
base = 0
drop(1, 2)
=
2
drop(2, 3)
=
5
drop(6, 1)
=
?
2
3
max 5
1
2
3
4
5
6
7
landed!
range [4..4] now has height
1
drop(1, 2)
=
2
drop(2, 3)
=
5
drop(6, 1)
=
5
2
3
max 5
1
2
3
4
5
6
7
ans =
[2, 5, 5]
algo
master
.
io
Step:
Start: Process falling squares and track the maximum stack height after each drop.
0 / 17
Input
Standard
Stacking
Adjacent
Overlapping
Custom
positions
=
[[1,2],[2,3],[6,1]]
0 / 17
algo
master
.
io
Step:
Start: Process falling squares and track the maximum stack height after each drop.
