📖 6 min read
Last updated on

Largest Rectangle in Histogram — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer says: “Find the largest rectangle that can be formed in a histogram.” This is one of the most elegant monotonic stack problems. For each bar, you need to determine how far left and right it can extend at its own height. A monotonic increasing stack gives you both boundaries in O(n) total. Largest Rectangle in Histogram is LeetCode #84, a Hard problem with a surprisingly clean solution once you see the pattern.

This walkthrough covers the stack invariant, the sentinel trick, and the width formula that candidates consistently get wrong under pressure.

The Problem

Given an array of integers heights representing the heights of bars in a histogram (each bar has width 1), return the area of the largest rectangle that can be formed within the histogram. (LeetCode #84)

Example 1

Input heights = [2,1,5,6,2,3]

Output 10

The largest rectangle spans bars at indices 2 and 3 (heights 5 and 6), limited by height 5, giving area 5 * 2 = 10.

Example 2

Input heights = [2,4]

Output 4

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Largest Rectangle in Histogram is the canonical monotonic stack problem. Interviewers use it to test whether you can maintain a stack invariant, compute boundaries from stack state, and handle the “flush remaining elements” edge case cleanly.

SkillWhat Interviewers Observe
Monotonic stackDo you recognize and implement the increasing-stack approach?
Stack invariantCan you articulate what the stack contains at each step?
Left and right boundariesDo you correctly compute the width for each popped bar?
Sentinel valuesDo you append a 0 at the end to flush remaining bars?
Brute force firstDo you mention O(n^2) brute force before the O(n) solution?

Step 1: Clarifying Questions

  1. Can heights be 0? Yes. A bar of height 0 effectively resets the histogram.

  2. Is each bar’s width always 1? Yes.

  3. Can the array be empty? n >= 1 is guaranteed.

Step 2: A First (Non-Optimal) Idea

For each bar i, expand left and right while the neighboring bars are at least as tall as heights[i]. The rectangle width is the expansion range, and the height is heights[i]. Take the maximum area.

def largestRectangleArea_brute(heights):
    max_area = 0
    for i in range(len(heights)):
        left = right = i
        while left > 0 and heights[left - 1] >= heights[i]:
            left -= 1
        while right < len(heights) - 1 and heights[right + 1] >= heights[i]:
            right += 1
        max_area = max(max_area, heights[i] * (right - left + 1))
    return max_area
ApproachTimeSpace
Expand from each barO(n^2)O(1)
Monotonic stackO(n)O(n)

Step 3: The Key Insight

For each bar i, the largest rectangle using heights[i] as the limiting height extends left until it hits a shorter bar, and right until it hits a shorter bar. A monotonic increasing stack gives these boundaries efficiently: when a bar is popped (because a shorter bar arrived from the right), the current index is the right boundary and the new top of the stack is the left boundary.

The stack stores indices in increasing height order. When we encounter a bar shorter than the stack top, we pop and compute the rectangle for the popped bar.

Histogram bars [2,1,5,6,2,3] with bars at indices 2-3 highlighted showing the largest rectangle area of 10. ---

Step 4: Algorithm

Maintain a stack of indices in increasing height order. Append a sentinel 0 to heights to flush all remaining bars at the end.

For each index i:

  • While the stack is non-empty and heights[i] < heights[stack[-1]]:
    • Pop the top index h_idx.
    • Height = heights[h_idx].
    • Right boundary = i.
    • Left boundary = stack[-1] if stack is non-empty, else -1.
    • Width = i - left_boundary - 1.
    • Update max area.
  • Push i.

Python Implementation

def largestRectangleArea(heights: list[int]) -> int:
    heights = heights + [0]  # sentinel to flush all bars
    stack = []  # monotonic increasing stack of indices
    max_area = 0

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Why this is interview-friendly:

  • Sentinel eliminates special-case handling. The trailing 0 forces all remaining bars to be popped from the stack. Without it, you’d need a separate pass after the main loop.
  • Each bar pushed and popped exactly once. Despite the nested while, the total work is O(n).
  • Width formula is compact. i - left - 1 where left is the new stack top (or -1 if empty). This covers all cases.

Time & Space Complexity

TimeSpace
Largest Rectangle in HistogramO(n)O(n)

Each bar is pushed onto and popped from the stack at most once. The stack holds at most n indices.

Common Interview Mistakes

  1. Not appending the sentinel 0. Without the trailing 0, bars that are never followed by a shorter bar never get popped. You’d miss rectangles involving the tallest bars. The sentinel forces all remaining bars to be processed.

  2. Wrong width formula. When popping index h_idx, the left boundary is the new top of the stack (the last bar shorter than heights[h_idx]), and the right boundary is i. Width = i - stack[-1] - 1 (or i - (-1) - 1 = i if the stack is empty).

  3. Confusing index vs. height on the stack. Push indices onto the stack, not heights. You need both the index (for width calculation) and the height (from heights[idx]).

  4. Not mentioning brute force first. Always state the brute-force (try every bar as the limiting height: O(n^2)) before the stack solution. This shows structured thinking and makes the O(n) solution more impressive.

What a Strong Candidate Sounds Like

“For each bar, the largest rectangle at its height extends left and right until it hits a shorter bar. I use a monotonic increasing stack of indices. When a shorter bar arrives at index i, I pop bars that are taller. For each popped bar, i is the right boundary and the new stack top is the left boundary. I append a 0 sentinel to handle bars that never encounter a shorter bar to their right. O(n) time, O(n) space.”

Example Interview Dialogue

Interviewer: Walk through [2, 1, 5, 6, 2, 3].

Candidate: Push 0 (h=2). At i=1, h=1 < h[0]=2: pop 0, left=-1, width=1-(-1)-1=1, area=2. Push 1 (h=1). Push 2 (h=5), push 3 (h=6). At i=4, h=2 < h[3]=6: pop 3, left=2, width=4-2-1=1, area=6. h=2 < h[2]=5: pop 2, left=1, width=4-1-1=2, area=10. Push 4 (h=2). Push 5 (h=3). Sentinel at i=6, h=0: pop 5, left=4, width=6-4-1=1, area=3. Pop 4, left=1, width=6-1-1=4, area=8. Pop 1, left=-1, width=6-(-1)-1=6, area=6. Maximum is 10.

Interviewer: What problem uses this as a subroutine?

Candidate: Maximal Rectangle (LeetCode #85). For a binary matrix, treat each row as a histogram base. For each row, compute the bar heights (consecutive 1s above) and run the largest rectangle in histogram algorithm. This gives the maximal rectangle in the matrix in O(rows * cols) time.

  • Maximal Rectangle (LeetCode #85). Apply this exact histogram algorithm row by row on a binary matrix.
  • Trapping Rain Water (LeetCode #42). Related two-pointer / stack problem on histogram-like arrays.
  • Daily Temperatures (LeetCode #739). Monotonic stack to find the next greater/smaller element.

Practice This in a Mock Interview

Largest Rectangle in Histogram is one of the hardest clean stack problems. The sentinel trick and the width formula are easy to get wrong under pressure. Trace through [2, 1, 5, 6, 2, 3] by hand several times until the pop-and-compute pattern is automatic.

Start a mock interview for Largest Rectangle in Histogram on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →