Largest Rectangle in Histogram
Use a monotonic stack to track left boundaries and compute the maximum area rectangle that fits within a histogram in a single pass.
Largest Rectangle in Histogram is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Problem: Largest Rectangle in Histogram
The Largest Rectangle in Histogram problem (LeetCode 84) gives an array of non-negative integers representing bar heights in a histogram where each bar has width 1. Find the area of the largest rectangle that can be formed within the histogram. The rectangle must span contiguous bars and its height is limited by the shortest bar it covers.
A brute-force approach: for every pair (i, j), compute the minimum height in [i, j] and multiply by (j - i + 1). This is O(n³) or O(n²) with pre-computed minimums — too slow. The monotonic stack solution runs in O(n).
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10Key Insight: What Limits Each Bar's Rectangle?
For each bar i with height h, the largest rectangle it can be the minimum of extends: leftward until the first bar shorter than h, and rightward until the first bar shorter than h. The width is right_boundary - left_boundary - 1 and the area is h × width.
This reframes the problem: for each bar, find its previous smaller element (PSE) and next smaller element (NSE). These are exactly what a monotonic increasing stack computes. The moment we pop bar i (because a shorter bar was found), the current bar is its NSE and the stack top after popping is its PSE.
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)One-Pass Solution with Monotonic Stack
The two-pass approach above works but can be merged into a single pass. Process bars left to right with a monotonic increasing stack. When bar i is shorter than the stack top, pop the stack top — the popped bar's height is the height of a rectangle, its right boundary is i, and its left boundary is the new stack top + 1.
A standard trick: append a sentinel 0 at the end of heights. This ensures all bars are popped from the stack at the end, even if no shorter bar appears naturally. Without the sentinel, you need a post-loop cleanup phase for remaining stack elements.
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 16Tracing the One-Pass Algorithm
Let us trace [2, 1, 5, 6, 2, 3, 0] (with sentinel) step by step:
- i=0, h=2: push 0. Stack: [0]
- i=1, h=1: pop 0 (h=2, width=1, area=2). Stack empty, push 1. Stack: [1]
- i=2, h=5: 5>1, push 2. Stack: [1,2]
- i=3, h=6: 6>5, push 3. Stack: [1,2,3]
- i=4, h=2: pop 3 (h=6,width=4-2-1=1,area=6), pop 2 (h=5,width=4-1-1=2,area=10★), 2>1 stop. Push 4. Stack: [1,4]
- i=5, h=3: 3>2, push 5. Stack: [1,4,5]
- i=6, sentinel h=0: pop all, computing areas...
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])Width Calculation: Why i - stack[-1] - 1?
When we pop bar j from the stack, we know: the right boundary of j's rectangle is i (the first bar shorter than j to the right). The left boundary is the bar immediately below j in the stack after the pop — call it k. The width is therefore i - k - 1 (bars from k+1 to i-1 inclusive).
If the stack is empty after the pop, j's rectangle extends all the way to the left edge (index 0). The width is simply i (indices 0 to i-1, all of which are at least as tall as heights[j]). This is the special case width = i if not stack else i - stack[-1] - 1.
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])Maximal Rectangle in Binary Matrix
Maximal Rectangle (LeetCode 85) extends the histogram problem to a 2D binary matrix. For each row, compute the height of consecutive 1s above each cell. This creates a histogram for that row. Apply the largest-rectangle-in-histogram algorithm to each row's histogram. The overall maximum across all rows is the answer.
This reduces a 2D problem to n repeated 1D histogram problems. Time complexity is O(m × n) for an m-row, n-column matrix — one histogram pass per row, each pass O(n).
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6Edge Cases in Histogram Problems
Important edge cases to handle:
- All same height: the entire array forms one rectangle; answer = n × height
- Monotonically increasing: no pop happens until the sentinel; last bar's area is the max
- Single bar: answer = height[0]
- Bars with height 0: they act as natural sentinels, splitting the histogram into independent segments
The sentinel (appending 0) at the end handles the monotonically increasing case by forcing all remaining bars to be popped at the end. Without it, you need a separate cleanup loop after the main iteration.
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)Divide and Conquer Alternative
The histogram problem can also be solved with divide and conquer: split at the minimum height bar, recursively solve each half, and compare with the rectangle spanning the full width using the minimum height. This gives O(n log n) average but O(n²) worst case for sorted inputs.
The monotonic stack approach is strictly better at O(n) worst case. However, understanding the divide-and-conquer approach deepens problem intuition and explains why the minimum height bar in any segment is always the limiting factor for full-width rectangles.
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10Histogram Pattern: Count of Subarrays
A related problem using the same stack technique: count the number of subarrays in a histogram where the minimum element equals some target. This is answered by computing PSE and NSE for each bar, then using the formula (i - pse[i]) × (nse[i] - i) which counts sub-histograms where bar i is the minimum.
This 'left count × right count' technique appears in several LeetCode problems: sum of subarray minimums (907), count of substrings with all unique characters, and contribution technique problems. The monotonic stack computes PSE and NSE in O(n) enabling O(1) per element contribution.
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444Practical Interview Tips
When you see a histogram problem in an interview, follow this checklist:
- Clarify: can heights be 0? What is the output — area, indices, or count?
- Start with brute force and state O(n²) or O(n³) complexity
- Mention that each bar's contribution depends on its left and right extent to the nearest shorter bar
- Introduce PSE/NSE → monotonic stack → O(n) solution
- Handle the sentinel trick (append 0) to simplify code
- Trace a small example on the whiteboard
Common follow-up: extend to 2D (maximal rectangle). Demonstrate that you can reduce it to n histogram problems, each O(n), for O(m×n) total.
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')Sum of Subarray Ranges and Similar Variants
The PSE/NSE technique generalises to several LeetCode problems. Sum of Subarray Ranges (2104) asks for the sum of (max - min) across all subarrays. This equals (sum of subarray maxima) minus (sum of subarray minima), each computed with a monotonic stack in O(n). Number of Visible People in a Queue (1944) uses a decreasing stack where each pop counts a visible person. Recognising this family of problems comes from noticing the phrase 'for each element, how far can it dominate?' — the answer is always PSE/NSE with a monotonic stack.
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: for each bar, its largest containing rectangle has boundaries defined by the nearest shorter bar on each side (PSE and NSE), a monotonic increasing stack computes all PSE/NSE boundaries in one O(n) pass by finding both as bars are popped, and appending a sentinel 0 ensures all bars are popped from the stack, simplifying the code to a single loop. Next up we apply the monotonic deque to solve sliding-window maximum in O(n).
Frequently asked questions
Is the “Largest Rectangle in Histogram” lesson free?
Yes — the full text of “Largest Rectangle in Histogram” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Largest Rectangle in Histogram”?
Use a monotonic stack to track left boundaries and compute the maximum area rectangle that fits within a histogram in a single pass. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Largest Rectangle in Histogram” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.