Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Largest Rectangle in Histogram

Stackshard

Given `heights`, the bar heights of a histogram (each bar 1 unit wide), implement `largestRectangle(heights)` returning the area of the largest rectangle that fits entirely within the bars.

Examples

Input: [2, 1, 5, 6, 2, 3]
Output: 10
Bars of heights 5 and 6 form a 5×2 = 10 rectangle.
Input: [2, 4]
Output: 4
The single bar of height 4 (width 1) loses to the 2×2 rectangle.

Sample tests

Input: largestRectangle([2,1,5,6,2,3])
Output: 10
Input: largestRectangle([2,4])
Output: 4

+ 2 hidden tests run on Submit.

Hints

Common pitfalls
  • Forgetting the sentinel `0` appended at the end leaves bars on the stack uncounted.
  • Computing the width from popped indices instead of the new stack top after popping.

Learning resources

  • Wikipedia: Stack (abstract data type)
Approach & explanation (try first)

A monotonic increasing stack of indices lets each bar be the limiting height of a rectangle exactly when a shorter bar forces it off the stack. The width spans from the element now on top (exclusive) to the current index (exclusive). Appending a trailing 0 flushes the stack. O(n).

Loading...
⌘/Ctrl + Enter

Run your code to see results.