Largest rectangle in a histogram - DSA Practice

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1 return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2, 1, 5, 6, 2, 3]

Output: 10

Explanation: The largest rectangle is highlighted, which has an area of 5*2 = 10 units.

Example 2:

Input: heights = [3, 5, 1, 7, 5, 9]

Output: 15

Explanation: The largest rectangle has an area of 5*3 = 15 units.

Now Your Turn!

Pick the correct output for the given input

Input: heights = [2,4]

8264

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

39. Largest rectangle in a histogram

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Hint 1

Hint 2

Frequently Occurring Doubts

Why do we need the next smaller elements for computing width?

What if all bars have the same height?

Interview Follow-up Questions

How would you extend this to a 2D matrix (maximal rectangle in a binary matrix)?

Can we find the second-largest rectangle efficiently?

Fun Facts

Fun Fact 1

Fun Fact 2