LeetCopilot Logo
LeetCopilot

3 Critical Mistakes in Largest Rectangle in Histogram (And How to Fix Them)

LeetCopilot Team
Dec 22, 2025
8 min read
Monotonic StackHistogramLargest RectangleCommon MistakesInterview Prep
Avoid the most common bugs in histogram problems: wrong width calculation, missing sentinels, and incorrect stack order. Learn the correct approach with detailed examples.
Complete Guide

The Complete Monotonic Stack & Queue Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to monotonic stacks and queues. Learn all variants, when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any monotonic stack/queue problem.

Read the complete guide

The Largest Rectangle in Histogram is one of the most elegant monotonic stack problems—and one of the easiest to get wrong.

Three critical mistakes cause 90% of wrong answers. Understanding and fixing them is the difference between AC (Accepted) and WA (Wrong Answer).

This guide shows you the exact mistakes, why they happen, and how to fix them permanently.

TL;DR

The 3 critical mistakes:

  1. Wrong width calculation (i - stack[-1] instead of i - stack[-1] - 1)
  2. Missing sentinels (not adding 0 at both ends)
  3. Wrong stack order (decreasing instead of increasing)

Quick fixes:

python
# Fix 1: Correct width
width = i - stack[-1] - 1  # Exclude boundaries

# Fix 2: Add sentinels
heights = [0] + heights + [0]

# Fix 3: Increasing stack
while stack and heights[i] < heights[stack[-1]]:
    # Process...

Mistake 1: Wrong Width Calculation

The Bug

❌ Wrong:

python
while stack and heights[i] < heights[stack[-1]]:
    h_idx = stack.pop()
    height = heights[h_idx]
    width = i - stack[-1]  # WRONG!
    area = height * width

Why It's Wrong

The boundaries are NOT included in the rectangle.

Visual:

code
Heights: [2, 1, 5, 6, 2, 3]
         [0  1  2  3  4  5]

Processing i=4 (height=2), popping index 3 (height=6):
  Left boundary: stack[-1] = 2 (height=5)
  Right boundary: i = 4 (height=2)
  
  Rectangle with height 6:
    Can only extend between boundaries
    NOT including boundaries
    
  Correct width: 4 - 2 - 1 = 1
  Wrong width: 4 - 2 = 2 (includes boundary!)

The Fix

✅ Correct:

python
width = i - stack[-1] - 1  # Subtract 1 to exclude boundaries

Why -1?

  • stack[-1] is the left boundary (next smaller to left)
  • i is the right boundary (next smaller to right)
  • Rectangle extends between boundaries, not including them
  • Distance between positions: right - left - 1

Complete Example

python
def largestRectangleArea(heights):
    heights = [0] + heights + [0]
    stack = []
    max_area = 0
    
    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h_idx = stack.pop()
            height = heights[h_idx]
            
            # CORRECT: Exclude boundaries
            width = i - stack[-1] - 1
            
            area = height * width
            max_area = max(max_area, area)
        
        stack.append(i)
    
    return max_area

Mistake 2: Missing Sentinels

The Bug

❌ Wrong:

python
def largestRectangleArea(heights):
    stack = []
    max_area = 0
    
    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h_idx = stack.pop()
            
            # What if stack is empty?
            if not stack:
                width = i  # Special case
            else:
                width = i - stack[-1] - 1
            
            area = heights[h_idx] * width
            max_area = max(max_area, area)
        
        stack.append(i)
    
    # What about remaining elements in stack?
    while stack:
        h_idx = stack.pop()
        if not stack:
            width = len(heights)
        else:
            width = len(heights) - stack[-1] - 1
        area = heights[h_idx] * width
        max_area = max(max_area, area)
    
    return max_area

Problems:

  • Complex edge case handling
  • Easy to make off-by-one errors
  • Need to process remaining stack separately

The Fix: Add Sentinels

✅ Correct:

python
def largestRectangleArea(heights):
    # Add sentinels: 0 at both ends
    heights = [0] + heights + [0]
    stack = []
    max_area = 0
    
    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h_idx = stack.pop()
            height = heights[h_idx]
            width = i - stack[-1] - 1
            area = height * width
            max_area = max(max_area, area)
        
        stack.append(i)
    
    # No need to process remaining stack
    # Sentinels ensure all bars are processed
    
    return max_area

Why Sentinels Work

Left sentinel (0 at start):

  • Ensures stack is never empty when calculating width
  • Acts as left boundary for all bars

Right sentinel (0 at end):

  • Forces all remaining bars to be processed
  • Acts as right boundary for all bars

Visual:

code
Original: [2, 1, 5, 6, 2, 3]
With sentinels: [0, 2, 1, 5, 6, 2, 3, 0]
                [0  1  2  3  4  5  6  7]

When processing right sentinel (i=7, height=0):
  All bars in stack are popped
  Stack always has at least index 0 (left sentinel)
  No special case handling needed

Mistake 3: Wrong Stack Order

The Bug

❌ Wrong:

python
# Using decreasing stack (wrong for histogram!)
while stack and heights[i] > heights[stack[-1]]:
    # This finds next GREATER, not next SMALLER
    stack.pop()

Why It's Wrong

For histogram, we need INCREASING stack to find next smaller elements.

Reasoning:

  • Rectangle height is limited by the shortest bar
  • We need to find when a shorter bar appears
  • Shorter bar = next SMALLER element
  • Next smaller requires INCREASING stack

The Fix

✅ Correct:

python
# Use increasing stack
while stack and heights[i] < heights[stack[-1]]:
    # Pop when current is SMALLER
    h_idx = stack.pop()
    # Calculate area with h_idx as height

Comparison

ProblemStack OrderPopping Condition
Next Greater ElementDecreasingnums[i] > stack[-1]
HistogramIncreasingheights[i] < stack[-1]
Next Smaller ElementIncreasingnums[i] < stack[-1]

Complete Correct Solution

python
def largestRectangleArea(heights):
    """
    LeetCode #84: Largest Rectangle in Histogram
    
    Approach: Monotonic increasing stack
    - For each bar, find next smaller on both sides
    - Calculate area with current bar as height
    
    Time: O(n)
    Space: O(n)
    """
    # Add sentinels
    heights = [0] + heights + [0]
    stack = []
    max_area = 0
    
    for i in range(len(heights)):
        # Increasing stack: pop when current is smaller
        while stack and heights[i] < heights[stack[-1]]:
            h_idx = stack.pop()
            height = heights[h_idx]
            
            # Width: exclude boundaries
            width = i - stack[-1] - 1
            
            area = height * width
            max_area = max(max_area, area)
        
        stack.append(i)
    
    return max_area

# Test
print(largestRectangleArea([2, 1, 5, 6, 2, 3]))
# Output: 10

Step-by-Step Trace

code
Heights: [0, 2, 1, 5, 6, 2, 3, 0]
         [0  1  2  3  4  5  6  7]

i=0, h=0: stack=[0]
i=1, h=2: 2 > 0, stack=[0,1]
i=2, h=1: 
  1 < 2, pop 1, height=2, width=2-0-1=1, area=2×1=2
  1 > 0, stack=[0,2]
i=3, h=5: 5 > 1, stack=[0,2,3]
i=4, h=6: 6 > 5, stack=[0,2,3,4]
i=5, h=2:
  2 < 6, pop 4, height=6, width=5-3-1=1, area=6×1=6
  2 < 5, pop 3, height=5, width=5-2-1=2, area=5×2=10 ← MAX
  2 > 1, stack=[0,2,5]
i=6, h=3: 3 > 2, stack=[0,2,5,6]
i=7, h=0:
  0 < 3, pop 6, height=3, width=7-5-1=1, area=3×1=3
  0 < 2, pop 5, height=2, width=7-2-1=4, area=2×4=8
  0 < 1, pop 2, height=1, width=7-0-1=6, area=1×6=6
  stack=[0]

Maximum area: 10 ✓

Edge Cases

Edge Case 1: Single Bar

python
heights = [5]
# With sentinels: [0, 5, 0]
# Area: 5 × 1 = 5 ✓

Edge Case 2: All Same Height

python
heights = [3, 3, 3, 3]
# Maximum: 3 × 4 = 12 ✓

Edge Case 3: Strictly Increasing

python
heights = [1, 2, 3, 4, 5]
# Maximum: 3 × 3 = 9 (middle bar)

Edge Case 4: Strictly Decreasing

python
heights = [5, 4, 3, 2, 1]
# Maximum: 5 × 1 = 5 (tallest bar)

Debugging Checklist

When your histogram solution fails:

  • Width calculation: Using i - stack[-1] - 1?
  • Sentinels: Added 0 at both ends?
  • Stack order: Increasing (not decreasing)?
  • Popping condition: < (not >)?
  • Edge cases: Tested single bar, all same, increasing, decreasing?

Related Problems

Same pattern:

  1. Maximal Rectangle (#85) - 2D histogram
  2. Largest Rectangle in Histogram (#84) - Original
  3. Maximum Binary Tree (#654) - Tree construction

Conclusion

Histogram problems have 3 critical mistakes that cause most failures.

The fixes:

  1. Width: i - stack[-1] - 1 (exclude boundaries)
  2. Sentinels: [0] + heights + [0] (simplify edge cases)
  3. Stack order: Increasing (for next smaller)

The template:

python
heights = [0] + heights + [0]
stack = []
max_area = 0

for i in range(len(heights)):
    while stack and heights[i] < heights[stack[-1]]:
        h_idx = stack.pop()
        height = heights[h_idx]
        width = i - stack[-1] - 1
        area = height * width
        max_area = max(max_area, area)
    stack.append(i)

return max_area

Master these fixes, and you'll never fail histogram problems again.

Next steps:

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials