Problem

We are given an array heights, where heights[i] represents the height of a histogram bar. Each bar has a width of 1.

We need to return the area of the largest rectangle that can be formed using one or more consecutive bars.

For example:

heights = [7, 1, 7, 2, 2, 4]

The answer is:

8

Because the largest rectangle can be formed using bars of height 2 across width 4.

Brute Force Approach

The first idea is to treat each bar as the minimum height of a rectangle.

For every index i, we take heights[i] as the rectangle height. Then we expand to the left and right while the neighboring bars are at least this tall.

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        n = len(heights)

        for i in range(n):
            height = heights[i]

            rightMost = i + 1
            while rightMost < n and heights[rightMost] >= height:
                rightMost += 1

            leftMost = i
            while leftMost >= 0 and heights[leftMost] >= height:
                leftMost -= 1

            rightMost -= 1
            leftMost += 1

            area = height * (rightMost - leftMost + 1)
            maxArea = max(maxArea, area)

        return maxArea

For each bar, we scan left and right to find how far the rectangle can extend.

Time Complexity

For each index, we may scan the whole array.

O(n^2)

Space Complexity

O(1)

This works, but it can be slow for larger inputs.

Why we need +1 in             

area = height * (rightMost - leftMost + 1)

The +1 is needed because both leftMost and rightMost are inclusive indices.

After these adjustments:

rightMost -= 1
leftMost += 1

both variables point to bars that are actually part of the rectangle.

So the width is:

rightMost - leftMost + 1

Example

Suppose the rectangle spans indices:

Index:   0 1 2 3 4
Bars:      █ █ █
          ^     ^
      leftMost rightMost

Here,

leftMost = 1
rightMost = 3

The rectangle covers:

  • index 1
  • index 2
  • index 3

That’s 3 bars, not:

3 - 1 = 2

because subtraction only tells you the distance between the endpoints.

You need:

width = 3 - 1 + 1 = 3

Why do we subtract and add first?

Notice your search loops stop one step too far:

while rightMost < n and heights[rightMost] >= height:
    rightMost += 1

When the loop ends, rightMost is either:

  • the first smaller bar, or
  • n

So you move back one position:

rightMost -= 1

Similarly,

while leftMost >= 0 and heights[leftMost] >= height:
    leftMost -= 1

When this loop ends, leftMost is the first smaller bar (or -1), so you move forward:

leftMost += 1

Now both leftMost and rightMost are included in the rectangle, which is why the width formula is:

width = rightMost - leftMost + 1
area = height * width

A good rule to remember is:

  • Inclusive range (left and right are both included): right - left + 1
  • Exclusive range (right is one past the end, like Python slicing): right - left

In your brute-force solution, you’re working with an inclusive range, so the +1 is required.

Optimized Approach: Monotonic Stack

We can solve this more efficiently using a monotonic increasing stack.

The stack stores pairs:

(index, height)

The idea is:

  • Keep bars in increasing height order.
  • When we find a smaller bar, it means the previous taller bars cannot extend any further to the right.
  • So we pop those taller bars and calculate their rectangle area.
  • The popped bar’s start index is reused because the current shorter bar can extend back to that position.
from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []

        for currIndex, currHeight in enumerate(heights):
            start = currIndex

            while stack and currHeight < stack[-1][1]:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (currIndex - index))
                start = index

            stack.append((start, currHeight))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))

        return maxArea

Why This Works

When the current height is smaller than the height at the top of the stack, the taller bar cannot continue further.

So we calculate its area immediately:

height * (currIndex - index)

Here:

  • height is the height of the rectangle.
  • currIndex - index is the width.
  • index is where this height started.

After popping, we update:

start = index

This allows the current shorter bar to extend further left.

At the end, some bars may still remain in the stack. These bars can extend until the end of the histogram, so we calculate their areas separately.

Example Walkthrough

For:

heights = [7, 1, 7, 2, 2, 4]

When we see 1, we know the previous 7 cannot extend anymore, so we calculate:

7 * 1 = 7

Later, when we see 2, the previous 7 also cannot continue, so we calculate:

7 * 1 = 7

The bars with height 2 can extend across multiple positions, giving:

2 * 4 = 8

So the final answer is:

8

Complexity

Time Complexity

O(n)

Each bar is pushed into the stack once and popped at most once.

Space Complexity

O(n)

In the worst case, the stack may store all bars.

Final Thoughts

The brute force solution is easier to understand because it directly checks how far each bar can expand.

The optimized monotonic stack solution is more efficient because it avoids repeated scanning. It calculates the largest possible rectangle for each bar exactly when that bar can no longer extend to the right.