Given an array of heights representing a histogram, find the area of the largest rectangle that fits entirely within the histogram, where each bar has width 1.
This is LeetCode 84, and it is the question that defined the monotonic stack pattern in the modern interview canon. Before this problem, monotonic stacks were a niche data structure mostly mentioned in competitive programming circles. After this problem became a FAANG staple, monotonic stacks became one of the standard interview patterns, and a whole family of related problems (next greater element, daily temperatures, sliding window maximum) became canonical applications of the same technique.
The setup
Input: [2, 1, 5, 6, 2, 3]
Output: 10
The 5 and 6 form a rectangle of width 2 and height 5, area 10. That is the largest rectangle in the histogram.
The problem is short and the answer is a single number, but the journey from the brute force to the optimal solution is one of the steepest in the LeetCode canon, which is exactly why interviewers love it.
Brute force: O(n²)
def largest_brute(heights):
n = len(heights)
best = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
best = max(best, min_h * (j - i + 1))
return best
For each starting index, expand rightward while tracking the minimum height. The area at any width is the running minimum times the width. O(n²) time, O(1) space.
This is the first solution most candidates produce. It is correct and gets partial credit. Interviewers expect a candidate to state this within five minutes, then start optimizing.
Divide and conquer: O(n log n) average, O(n²) worst case
Find the index of the minimum height in the range. The largest rectangle either spans the minimum (with width = full range, height = min), or lies entirely to the left or right of it. Recurse on left and right.
def largest_dc(heights, lo=0, hi=None):
if hi is None: hi = len(heights) - 1
if lo > hi: return 0
min_idx = lo
for i in range(lo + 1, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
span = heights[min_idx] * (hi - lo + 1)
left = largest_dc(heights, lo, min_idx - 1)
right = largest_dc(heights, min_idx + 1, hi)
return max(span, left, right)
O(n log n) on average. Worst case (sorted input) is O(n²) because the minimum is always at one end. With a segment tree for range-minimum queries, this becomes O(n log n) reliably, but at the cost of complicated infrastructure.
This is the rare middle-tier solution. Few candidates produce it; most go directly from brute force to monotonic stack. The interviewer rarely asks for it explicitly.
Monotonic stack: O(n)
The key insight: for each bar, the largest rectangle that has that bar as its shortest bar extends as far left as the first shorter bar and as far right as the next shorter bar. If we know, for every bar, the index of the previous shorter bar and the next shorter bar, we can compute the answer in O(n).
A monotonic stack computes both of those in one pass.
def largest_stack(heights):
n = len(heights)
stack = []
best = 0
for i in range(n + 1):
h = heights[i] if i < n else 0
while stack and heights[stack[-1]] > h:
top = stack.pop()
width = i if not stack else i - stack[-1] - 1
best = max(best, heights[top] * width)
stack.append(i)
return best
The stack stores indices of bars in increasing order of height. When we encounter a bar shorter than the top of the stack, we pop the top and compute the rectangle that has the popped bar as its shortest member: width is from one past the new top of the stack to i - 1. The sentinel 0 at the end of the iteration ensures all remaining bars in the stack are processed.
O(n) time because each bar is pushed and popped at most once. O(n) space for the stack in the worst case (sorted input).
Why this is the monotonic stack canon
The monotonic stack pattern is: maintain a stack where the elements are monotonically increasing (or decreasing). When a new element violates the monotonicity, pop elements from the stack and process them. The pattern shows up in dozens of problems:
- Next Greater Element (LeetCode 496)
- Daily Temperatures (LeetCode 739)
- Largest Rectangle in Histogram (LeetCode 84)
- Maximal Rectangle in 2D Matrix (LeetCode 85)
- Trapping Rain Water (LeetCode 42, alternative solution)
- Sum of Subarray Minimums (LeetCode 907)
- 132 Pattern (LeetCode 456)
- Sliding Window Maximum (LeetCode 239, with monotonic deque)
Largest rectangle in histogram is the canonical example because the connection between “shortest bar” and “previous/next shorter bar” is the cleanest possible motivation for the pattern. Once a candidate sees this problem solved with a monotonic stack, the pattern click for next-greater-element problems is much faster.
The 2D extension
Maximal Rectangle (LeetCode 85) takes a 2D binary matrix and asks for the largest all-1s rectangle. The trick: treat each row as the base of a histogram where each column’s height is the number of consecutive 1s ending at that row. Apply largest-rectangle-in-histogram to each row’s histogram. O(rows × cols) total.
def maximal_rectangle(matrix):
if not matrix: return 0
cols = len(matrix[0])
heights = [0] * cols
best = 0
for row in matrix:
for j in range(cols):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
best = max(best, largest_stack(heights))
return best
The 2D version is a standard senior-tier follow-up. Candidates who have nailed the 1D version and articulate the 2D extension are at the strong-staff level.
What interviewers grade
The signal layers in a strong answer:
- Brute force in 5 minutes. Producing the O(n²) solution within the first phase is the bar.
- Articulating the monotonic stack insight. “For each bar, the rectangle it dominates extends to the previous and next shorter bars.” Candidates who articulate this without writing code show real understanding.
- Clean stack code. The off-by-ones (sentinel value at the end, the width formula
i - stack[-1] - 1when the stack is non-empty) are vicious. Getting them right under pressure is the hardest part. - Correct complexity statement. O(n) time, O(n) space. Many candidates incorrectly state O(n log n).
- Edge cases. Empty input, all bars equal, single bar, decreasing input, increasing input. A polished candidate runs through these.
Common bugs
- Forgetting the sentinel. Without the
0at the end of iteration, bars remaining in the stack at the end are never processed, and the answer can be wrong if the largest rectangle is anchored at the right edge. - Wrong width formula. When the stack is empty after a pop, the width is
i(everything from index 0 toi-1). When the stack is non-empty, the width isi - stack[-1] - 1. Mixing these up gives off-by-one errors. - Strict vs. non-strict comparison. The condition for popping is
heights[stack[-1]] >= horheights[stack[-1]] > h; both work but require slightly different width formulas. Sticking to>is conventional. - Off-by-one in the iteration bound. Iterating to
n(inclusive) is required to process the sentinel; iterating ton - 1misses it.
Is it asked in 2026?
Yes, frequently. Largest rectangle in histogram is a senior-tier FAANG question that appears in onsite loops at Google, Meta, Amazon, Microsoft, Apple, and most AI labs and tier-2 tech firms. The 2D version is a staff-tier follow-up. The problem has not aged out because the monotonic stack pattern is genuinely useful in real systems work — sliding window analytics, rate limiters, and certain database query optimizations all use stack-like data structures with similar invariants.
Phone screens rarely use this problem; it is too long for a 45-minute slot. The natural home is a 60-minute onsite round where the interviewer expects to see brute force, the monotonic stack derivation, the code, and possibly the 2D extension as a stretch follow-up.
Frequently Asked Questions
What is the time complexity of the monotonic stack solution?
O(n). Each bar is pushed and popped at most once, so the total work is linear despite the inner while loop.
Why does the monotonic stack pattern appear in so many problems?
Because many array problems have the structure “for each element, find the nearest element with property X”. A monotonic stack answers this in O(n) for “X = greater” or “X = smaller”. The pattern generalizes broadly.
Is divide and conquer ever the right answer?
It is correct but suboptimal. The monotonic stack solution is strictly better in time and conceptually cleaner. Mention divide and conquer as a stepping stone if you cannot get to the stack solution, but do not stop there.
Can I solve this with a segment tree?
Yes, with range-minimum queries and recursion you get O(n log n). Strictly worse than the stack solution but works.
Is this still asked in 2026?
Yes, it is one of the most-asked Hard problems on the LeetCode top 100. Senior-tier FAANG, AI labs, and fintech all use it.