Largest Rectangle in Histogram

Difficulty: Hard Source: NeetCode

Problem

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1: Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The rectangle has height 5 and spans bars at indices 2 and 3.

Example 2: Input: heights = [2,4] Output: 4

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Monotonic stack — A stack maintained in sorted order to efficiently find the nearest smaller element to the left and right.
• Rectangle area reasoning — Understanding that a rectangle’s height is limited by the shortest bar it spans.

1. Brute Force

Intuition

For every pair of bars (i, j), the largest rectangle that spans from i to j has a height equal to the minimum bar height in that range. Try every possible left and right boundary and compute the area. Simple but slow.

Algorithm

1. For each starting bar i, track the running minimum height as you extend right.
2. For each ending bar j >= i, compute area = min_height * (j - i + 1).
3. Track the global maximum.

Solution

def largestRectangleArea_brute(heights):
    n = len(heights)
    max_area = 0

    for i in range(n):
        min_height = heights[i]
        for j in range(i, n):
            min_height = min(min_height, heights[j])
            area = min_height * (j - i + 1)
            max_area = max(max_area, area)

    return max_area


# Test cases
print(largestRectangleArea_brute([2, 1, 5, 6, 2, 3]))  # Expected: 10
print(largestRectangleArea_brute([2, 4]))               # Expected: 4
print(largestRectangleArea_brute([1]))                  # Expected: 1

Complexity

• Time: O(n²) — two nested loops over n bars.
• Space: O(1) extra.

2. Monotonic Increasing Stack

Intuition

For each bar, the largest rectangle with that bar as the shortest (limiting) bar extends as far left and right as possible — until it hits a bar shorter than itself. The right boundary is the first bar to the right that is shorter. The left boundary is the first bar to the left that is shorter.

A monotonic increasing stack gives you the left boundary for free: when you push a bar, everything below it in the stack is shorter (so it extends left past all of them). When a bar is popped because a shorter bar arrived, the shorter bar is the right boundary, and the new stack top is the left boundary.

The trick for the “extended left” part: instead of storing just the index, store (index, height) where index is the leftmost position the bar could extend to. When you pop a bar and the incoming bar is shorter, set the incoming bar’s start index to the popped bar’s start index (it can extend as far left as the popped bar could).

Algorithm

1. Initialize max_area = 0 and an empty stack of (start_index, height).
2. For each bar at index i with height h:
   • Set start = i.
   • While stack is non-empty and stack[-1][1] > h (current bar is shorter):
     • Pop (idx, popped_h).
     • Compute area = popped_h * (i - idx).
     • Update max_area.
     • Set start = idx (the current bar can extend as far left as the popped bar).
   • Push (start, h).
3. After the loop, process remaining bars in the stack:
   • For each (idx, h) in stack: area = h * (n - idx).
4. Return max_area.

Solution

def largestRectangleArea(heights):
    n = len(heights)
    max_area = 0
    # Stack stores (start_index, height)
    # Heights in stack are non-decreasing (monotonic increasing)
    stack = []

    for i, h in enumerate(heights):
        start = i
        # Pop all bars taller than the current bar
        while stack and stack[-1][1] > h:
            idx, popped_h = stack.pop()
            # Rectangle: height=popped_h, width=i-idx
            max_area = max(max_area, popped_h * (i - idx))
            # Current bar can extend as far left as this popped bar
            start = idx
        stack.append((start, h))

    # Remaining bars extend all the way to the right end
    for idx, h in stack:
        max_area = max(max_area, h * (n - idx))

    return max_area


# Test cases
print(largestRectangleArea([2, 1, 5, 6, 2, 3]))  # Expected: 10
print(largestRectangleArea([2, 4]))               # Expected: 4
print(largestRectangleArea([1]))                  # Expected: 1
print(largestRectangleArea([6, 2, 5, 4, 5, 1, 6]))  # Expected: 12
print(largestRectangleArea([1, 1, 1, 1]))         # Expected: 4
print(largestRectangleArea([5, 4, 3, 2, 1]))      # Expected: 9

Complexity

• Time: O(n) — each bar is pushed once and popped at most once.
• Space: O(n) — the stack holds at most n bars.

Common Pitfalls

Forgetting to process bars remaining in the stack after the loop. Bars still in the stack have not found a shorter right boundary — they extend all the way to the rightmost bar. Their area is height * (n - start_index).

Computing width incorrectly. When popping bar at idx due to the bar at i, the rectangle spans from idx to i - 1, so width is i - idx (not i - idx + 1, because the current shorter bar at i is not included).

Using >= instead of > when popping. You should only pop when the stack top is strictly taller than the current bar. If they are equal height, the current bar extends the same rectangle leftward, and the start update handles this correctly without needing an extra pop.

Storing only heights instead of (start, height) pairs. Without the start index, you cannot know how far left a bar’s rectangle extends after its left neighbors have been popped.