Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Largest Rectangle in Histogram
Bookmark
Brute Force
Divide & Conquer
Monotonic Stack
Sentinel
Input
Example 1
Example 2
Example 3
Ascending
Descending
Custom
heights
=
[2, 1, 5, 6, 2, 3]
histogram
2
1
5
6
2
3
0
1
2
3
4
5
the biggest rectangle that fits under the bars
histogram
2
1
5
6
2
3
0
1
2
3
4
5
the biggest rectangle that fits under the bars
max area =
2
histogram
2
1
5
6
2
3
2 × 1 = 2
0
1
2
3
4
5
i
left
right
area =
2
×
1
=
2
max area =
2
histogram
2
1
5
6
2
3
max 2
1 × 1 = 2
0
1
2
3
4
5
i
left
right
extend left →
[0, 1]
max area =
2
histogram
2
1
5
6
2
3
max 2
1 × 1 = 2
0
1
2
3
4
5
i
left
right
extend right →
[0, 4]
max area =
6
histogram
2
1
5
6
2
3
1 × 6 = 6
0
1
2
3
4
5
i
left
right
area =
1
×
6
=
6
max area =
10
histogram
2
1
5
6
2
3
5 × 2 = 10
0
1
2
3
4
5
i
left
right
area =
5
×
2
=
10
max area =
10
histogram
2
1
5
6
2
3
max 10
6 × 1 = 6
0
1
2
3
4
5
i
left
right
area =
6
×
1
=
6
max area =
10
histogram
2
1
5
6
2
3
max 10
2 × 1 = 6
0
1
2
3
4
5
i
left
right
extend left →
[2, 4]
max area =
10
histogram
2
1
5
6
2
3
max 10
2 × 4 = 8
0
1
2
3
4
5
i
left
right
area =
2
×
4
=
8
max area =
10
histogram
2
1
5
6
2
3
max 10
0
1
2
3
4
5
largest rectangle =
10
algo
master
.
io
Step:
Brute force: try every bar as the shortest bar of a rectangle.
0 / 23
Input
Example 1
Example 2
Example 3
Ascending
Descending
Custom
heights
=
[2, 1, 5, 6, 2, 3]
0 / 23
algo
master
.
io
Step:
Brute force: try every bar as the shortest bar of a rectangle.
