Largest rectangle in a histogram
Coding problemHardAsked in: Google, Microsoft, NPCI
A histogram is a row of bars, each one unit wide, with the heights given in the list. Return the area of the largest rectangle that fits completely inside the histogram. The rectangle's sides follow the grid: it covers some run of consecutive bars, and its height is at most the shortest bar in that run.
An empty histogram gives 0.
Examples
Example 1
Input: heights = [2,1,5,6,2,3]
Output: 10
The bars of height 5 and 6 hold a rectangle of height 5 and width 2.
Example 2
Input: heights = [2,4]
Output: 4
Example 3
Input: heights = [3,3,3]
Output: 9
Constraints
- The list holds between 0 and 100,000 values
- Each height is between 0 and 10,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.