Largest Rectangle In Histogram

1. Define the problem

You are given the heights of bars standing side by side, each one unit wide. Find the area of the largest rectangle that fits entirely inside the bars. A rectangle can span several bars, but its height can never be taller than the shortest bar it covers. So for every bar, the best rectangle using that bar as its height stretches left and right until it hits a bar that is shorter. A monotonic stack finds those two edges in one pass. Keep the positions of bars in a stack whose heights only ever increase from bottom to top. When a shorter bar arrives, every taller bar on the stack has just found its right edge, so pop it and measure its rectangle. Its left edge is the position of the bar still under it on the stack, so the width is right edge minus left edge minus one.

Constraints

1 ≤ heights.length ≤ 10⁵
0 ≤ heights_i ≤ 10⁴
Every bar is exactly one unit wide
The rectangle must sit on the same baseline as the bars

Example

Inputheights = [2, 1, 5, 6, 2, 3]

Output10

Explanation The bars at positions 2 and 3 are 5 and 6 tall. A rectangle of height 5 across both of them has area 5 * 2 = 10, which is the best possible.

2. Know the words first

In plain terms

Histogram: A row of bars standing on the same baseline. Here every bar is exactly one unit wide.
Monotonic stack: A stack that is deliberately kept in order — here the bar heights only increase from the bottom to the top. Anything that would break the order gets popped first.
Index: The position of a bar in the list, counting from 0. The stack stores positions, not heights.
Width: How many bars a rectangle covers. It is the distance between the first shorter bar on the left and the first shorter bar on the right, minus the edges themselves.

3. Visualize the solution

The row is the stack of bar positions, bottom-left to top-right

0—

1—

2—

3—

4—

5—

Statusinit

Start with an empty stack and a best area of 0.

What happens in this step

heights = [2, 1, 5, 6, 2, 3]
stack = []
best = 0

No bar has been visited yet, so every slot shows a dash.

Step 1 of 8

Steps to visualize

Each filled cell reads i<position> h<height>, so i2 h5 means the bar at position 2 is 5 tall. A dash means an empty slot.
Heights increase as you move right along the stack; that is what makes it monotonic.
While the new bar is shorter than the top of the stack, pop the top — it has found its right edge.
The popped bar stretches left to just after whatever is now on top, so width = current position - new top - 1.
Multiply the popped height by that width and keep the best area seen.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the stack of bar positions, bottom-left to top-right

0—

1—

2—

3—

4—

5—

Statusinit

Start with an empty stack and a best area of 0.

What happens in this step

heights = [2, 1, 5, 6, 2, 3]
stack = []
best = 0

No bar has been visited yet, so every slot shows a dash.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;

  for (let i = 0; i <= heights.length; i++) {
    const current = i === heights.length ? 0 : heights[i];

    while (stack.length > 0 && heights[stack[stack.length - 1]] >= current) {
      const height = heights[stack.pop()];
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      const width = i - left - 1;

      if (height * width > best) {
        best = height * width;
      }
    }

    stack.push(i);
  }

  return best;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`heights = [2, 1, 5, 6, 2, 3]`	`10`	example from the description
`heights = [7]`	`7`	smallest input, one bar on its own
`heights = [2, 4]`	`4`	a tall single bar beating a shorter pair
`heights = [3, 3, 3, 3]`	`12`	equal heights, where the whole row is one rectangle
`heights = [0, 0]`	`0`	bars with no height at all
`heights = [6, 5, 4, 3, 2, 1]`	`12`	heights that only fall, so every bar is popped as soon as it is passed

Largest Rectangle In Histogram