Largest Rectangle In Histogram

Hard · Stack

You are given a list of non-negative integers where each value represents the height of a bar in a histogram; every bar has width 1 and the bars stand side by side in order. Find the area of the largest rectangle that can be drawn using consecutive bars, where the rectangle's height cannot exceed the height of any bar it covers. Return that maximum area as an integer.

Examples

Input:  heights = [2,1,5,6,2,3]
Output: 10
Why:    The bars with heights 5 and 6 together form a rectangle of width 2 and height 5, giving area 10, which is the largest possible.

Input:  heights = [2,4]
Output: 4
Why:    Using only the bar of height 4 gives width 1 and height 4, area 4, which beats using both bars at height 2 (area 4 tie) but no combination exceeds 4.

Input:  heights = [0,0]
Output: 0
Why:    All bars have height 0 so any rectangle has zero area.

Constraints

1 <= heights.length <= 10^5, 0 <= heights[i] <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Largest Rectangle In Histogram

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Largest Rectangle In Histogram. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.