Largest Rectangle in Histogram – Solution & Complexity

Q: What is the time and space complexity of Largest Rectangle in Histogram?

The optimal Largest Rectangle in Histogram solution runs in `O(n)` time and `O(n)` space. Monotonic increasing stack of bar indices computes each bar's widest span.

Q: What is the most efficient way to solve Largest Rectangle in Histogram?

Monotonic increasing stack of bar indices computes each bar's widest span. This gives `O(n)` time complexity, and is a classic arrays and stack problem.

Q: How do you solve Largest Rectangle in Histogram in Python & JavaScript?

We provide a worked Largest Rectangle in Histogram solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Largest Rectangle in Histogram an easy or hard interview question?

Largest Rectangle in Histogram is generally rated **Hard**. It tests arrays and stack, which are common coding-interview patterns.

1. Understanding the Problem

Each bar has width 1 and a given height.
A rectangle spans a contiguous range of bars and its height is the shortest bar in that range.
We want the maximum possible height * width over all ranges.

2. The Key Insight

For each bar, imagine it is the limiting (shortest) bar of a rectangle.
That rectangle stretches left and right until it meets a strictly shorter bar.
If we know those left/right boundaries for every bar, the area is height * (right - left - 1).

3. Using a Monotonic Stack

Keep a stack of bar indices whose heights are increasing.
When the current bar is shorter than the bar on top of the stack, that top bar's rectangle must end here.
Pop it, compute its area, and repeat until the stack is increasing again.

def largest_rectangle_area(heights):
    stack = []  # indices of increasing bars
    best = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    return best

4. Draining the Stack with a Sentinel

After the loop, bars still on the stack never met a shorter bar to their right.
Appending a sentinel height of 0 forces every remaining bar to be popped and measured.
The width uses the array length as the right boundary.

def largest_rectangle_area(heights):
    stack = []
    best = 0
    for i, h in enumerate(heights + [0]):  # sentinel flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    return best

Largest Rectangle in Histogram – Solution & Complexity

1. Understanding the Problem

2. The Key Insight

3. Using a Monotonic Stack

4. Draining the Stack with a Sentinel

5. Complexity

FAQ

What is the time and space complexity of Largest Rectangle in Histogram?

What is the most efficient way to solve Largest Rectangle in Histogram?

How do you solve Largest Rectangle in Histogram in Python & JavaScript?

Is Largest Rectangle in Histogram an easy or hard interview question?