Largest Rectangle in Histogram – Learning the Monotonic Stack the Hard Way (LeetCode 84)

Problem Overview

The Largest Rectangle in Histogram problem is one of those classic questions that looks simple but exposes gaps in pattern recognition very quickly. You are given an array where each element represents the height of a bar in a histogram, and your task is to find the area of the largest rectangle that can be formed.

Initially, I had no intuition for this problem. I could brute-force it mentally, but nothing scalable came to mind. Only after revisiting monotonic stacks again did the solution start making sense.

---

Key Insight

Instead of trying to form rectangles explicitly, flip the thinking:

Assume each bar is the shortest bar in the rectangle.

Once you do that, the only thing you need to know is:

• The nearest smaller bar on the left
• The nearest smaller bar on the right

Between these two boundaries, the current bar can safely extend and form a rectangle. This transforms the problem into finding previous smaller and next smaller elements — a perfect use case for a monotonic stack.

---

Approach

1. Compute the index of the nearest smaller element to the right for every bar.
2. Compute the index of the nearest smaller element to the left for every bar.
3. For each bar, calculate the area assuming it is the minimum height.

The width of the rectangle becomes:

(right_smaller[i] - left_smaller[i] - 1)

And the area:

height[i] * width

---

Python Implementation

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        
        left_smaller = [-1] * len(heights)
        right_smaller = [len(heights)] * len(heights)
        stk = []
        
        # Nearest smaller to right
        for i in range(len(heights) - 1, -1, -1):
            while stk and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if stk:
                right_smaller[i] = stk[-1]
            stk.append(i)

        stk.clear()
        
        # Nearest smaller to left
        for i in range(len(heights)):
            while stk and heights[stk[-1]] >= heights[i]:
                stk.pop()
            if stk:
                left_smaller[i] = stk[-1]
            stk.append(i)
        
        ans = 0
        for i in range(len(heights)):
            current = heights[i] * (right_smaller[i] - left_smaller[i] - 1)
            ans = max(ans, current)

        return ans

---

Why This Works

The stack always maintains indices of bars in increasing order of height. When a smaller bar appears, it naturally defines a boundary where the current bar can no longer expand.

This ensures:

• Each element is pushed and popped only once
• Overall time complexity remains O(n)

---

What This Problem Taught Me

This wasn’t about memorizing a pattern. It was about realizing that some problems require you to stop thinking locally and instead assume a global role for each element.

Monotonic stacks don’t click immediately — but once they do, a whole category of problems starts looking familiar:

• Next Greater / Smaller Element
• Stock Span
• Maximal Rectangle

If you’re struggling with this problem, that’s normal. The intuition comes from repetition, not talent.

---

Source Code

Full implementation is available here:
https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC84.py