What is the brute force approach and complexity for Largest Rectangle in Histogram?

Fix the left edge, extend right, keep the minimum height so far with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Largest Rectangle in Histogram?

Pop a bar when a shorter one arrives; the arrival is its right wall, the new top is its left wall with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Largest Rectangle in Histogram?

Look for key signals in the prompt: "largest rectangle" indicates The height of a rectangle is the minimum bar it covers → think about each bar as the minimum.; "bars side by side" indicates A contiguous range. Each bar's range is limited by the nearest shorter bar on each side.; "up to 10^5 bars" indicates O(n²) is too slow. We need each bar's walls in O(1) amortized → monotonic stack..

Largest Rectangle in Histogram

Hard·LeetCode #84Basic Anchor

LeetCode

Jump:

30-Second Mental ModelMonotonic Stack (contribution / boundaries)

Complexity:O(N²)→O(N)

Key Insight

Keep a stack of indices with increasing heights. When bar i is shorter than (or equal to) the top, the top's rectangle can't go past i, so i is its right wall. Pop it. The bar now under it is shorter than it (the stack is increasing), so that is its left wall. Area = height × (i − left − 1). A fake bar of height 0 at i = n pops whatever is left.

Core Validity Invariant

The heights on the stack always increase from bottom to top. So the bar just under any bar is the nearest bar to its left that is shorter: its left wall.

Problem

You are given an array heights that describes a bar chart. Bar i has width 1 and height heights[i], and the bars stand side by side with no gaps.

Find the largest area of a rectangle that fits completely inside the bars. The rectangle covers whole bars that are next to each other, and it can be no taller than the shortest bar it covers.

Input

An integer array heights.

Output

One integer: the area of the largest rectangle.

Example 1

Input: heights = [2, 1, 5, 6, 2, 3]

Output: 10

Bars 5 and 6 (indices 2 and 3) are both at least 5 tall, so a rectangle of height 5 and width 2 fits: area 10. Nothing bigger fits.

Example 2

Input: heights = [2, 4]

Output: 4

Either the single bar 4 (area 4), or both bars at height 2 (area 2 × 2 = 4).

Constraints

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

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I pick a block of bars [l … r], how tall can the rectangle over that block be?
2.
Every rectangle has a shortest bar inside it. What if I made each bar "the shortest bar" in turn?
3.
If bar i is the shortest bar of the rectangle, how far left and right can the rectangle stretch?
4.
What stops the rectangle from stretching further?
5.
When I read a bar that is shorter than the bars before it, which earlier bars can no longer stretch to the right?

Brute force approach

Idea

A rectangle over bars [left … right] can be as tall as the shortest bar in that range. Fix left, then move right one bar at a time and keep the running minimum. Each step gives a candidate area minHeight × (right − left + 1).

Thinking process

1
A rectangle is decided by which bars it covers: a left edge and a right edge.
2
Its height is limited by the shortest bar it covers.
3
If I extend the right edge by one bar, the new minimum is just min(old minimum, new bar). No need to rescan.
4
So two loops, with a running min in the inner one.

Code & Implementation

brute.cpp

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int best = 0;

        // Try every left edge.
        for (int left = 0; left < n; left++) {
            int minHeight = INT_MAX;
            // Grow the right edge one bar at a time.
            // The rectangle can only be as tall as the shortest bar inside it.
            for (int right = left; right < n; right++) {
                minHeight = min(minHeight, heights[right]);
                best = max(best, minHeight * (right - left + 1));
            }
        }
        return best;
    }
};

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int best = 0;

        // Try every left edge.
        for (int left = 0; left < n; left++) {
            int minHeight = Integer.MAX_VALUE;
            // Grow the right edge one bar at a time.
            // The rectangle can only be as tall as the shortest bar inside it.
            for (int right = left; right < n; right++) {
                minHeight = Math.min(minHeight, heights[right]);
                best = Math.max(best, minHeight * (right - left + 1));
            }
        }
        return best;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        best = 0

        # Try every left edge.
        for left in range(n):
            min_height = float('inf')
            # Grow the right edge one bar at a time.
            # The rectangle can only be as tall as the shortest bar inside it.
            for right in range(left, n):
                min_height = min(min_height, heights[right])
                best = max(best, int(min_height) * (right - left + 1))

        return best

export function largestRectangleArea(heights: number[]): number {
    const n = heights.length;
    let best = 0;

    // Try every left edge.
    for (let left = 0; left < n; left++) {
        let minHeight = Infinity;
        // Grow the right edge one bar at a time.
        // The rectangle can only be as tall as the shortest bar inside it.
        for (let right = left; right < n; right++) {
            minHeight = Math.min(minHeight, heights[right]);
            best = Math.max(best, minHeight * (right - left + 1));
        }
    }
    return best;
}

Complexity

Time O(N²)Space O(1)

There are about n²/2 ranges. With n = 10^5 that is 5·10^9 steps, which is far too slow.

Better approach

Why brute force is slow

For every left edge, the brute force walks right over the same bars again, recomputing minimums it has already seen.

What repeated work are we doing?

Most ranges it checks are useless. For a fixed shortest bar, only the widest range where it is the shortest can be the answer, but brute force tries all the narrower ones too.

What information can we reuse?

Only n rectangles matter: one per bar, as wide as possible. Each one is decided by two walls, and a monotonic stack finds every wall in O(n) total.

New approach

Idea

Make each bar the shortest bar of its rectangle. Its rectangle then stretches to the walls: the nearest shorter bar on the left (prevSmaller[i]) and on the right (nextSmaller[i]). Find both arrays with a monotonic stack, then area = heights[i] × (nextSmaller[i] − prevSmaller[i] − 1).

Thinking process

1
The best rectangle has some shortest bar inside it. So if I try every bar as "the shortest", I will meet the best rectangle.
2
Once bar i is the shortest, I want the rectangle as wide as possible. It can cover every neighbour that is at least as tall as bar i.
3
It stops at the first shorter bar on each side. Those are "previous smaller" and "next smaller": the problems we already solved with a stack.
4
Pass 1 (left to right) gives prevSmaller, pass 2 (right to left) gives nextSmaller. Use −1 and n when there is no wall.
5
The bars strictly between the walls number next − prev − 1.

Visual

Pass 1 fills prevSmaller, pass 2 fills nextSmaller (−1 / n = no wall), pass 3 shades each bar's rectangle. The stack holds indices with heights increasing bottom → top; red cells were just popped.

Walls first, then areasheights = [2, 1, 5, 6, 2, 3]step 1/18

heights

▲i

prevSmaller

-1

nextSmaller

area

stack.idx

▲top

stack.val

Pass 1 (left → right)

height[i]: 2
popped: —
prevSmaller[0]: -1

Pass 1: prevSmaller[0] = -1

The stack is empty, so there is no shorter bar on the left: −1.

Code & Implementation

better.cpp

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> prevSmaller(n), nextSmaller(n);
        vector<int> st;   // indices; their heights increase bottom -> top

        // Pass 1: for each bar, the nearest bar on the LEFT that is shorter (-1 if none).
        for (int i = 0; i < n; i++) {
            // Bars at least as tall as heights[i] can't stop anyone to the right of i.
            while (!st.empty() && heights[st.back()] >= heights[i]) st.pop_back();
            prevSmaller[i] = st.empty() ? -1 : st.back();
            st.push_back(i);
        }

        st.clear();
        // Pass 2: for each bar, the nearest bar on the RIGHT that is shorter (n if none).
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && heights[st.back()] >= heights[i]) st.pop_back();
            nextSmaller[i] = st.empty() ? n : st.back();
            st.push_back(i);
        }

        // Pass 3: bar i is the shortest bar of the rectangle strictly between those two walls.
        int best = 0;
        for (int i = 0; i < n; i++) {
            int width = nextSmaller[i] - prevSmaller[i] - 1;
            best = max(best, heights[i] * width);
        }
        return best;
    }
};

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] prevSmaller = new int[n];
        int[] nextSmaller = new int[n];
        Deque<Integer> st = new ArrayDeque<>();   // indices; their heights increase bottom -> top

        // Pass 1: for each bar, the nearest bar on the LEFT that is shorter (-1 if none).
        for (int i = 0; i < n; i++) {
            // Bars at least as tall as heights[i] can't stop anyone to the right of i.
            while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
                st.pop();
            }
            prevSmaller[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        st.clear();
        // Pass 2: for each bar, the nearest bar on the RIGHT that is shorter (n if none).
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
                st.pop();
            }
            nextSmaller[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        // Pass 3: bar i is the shortest bar of the rectangle strictly between those two walls.
        int best = 0;
        for (int i = 0; i < n; i++) {
            int width = nextSmaller[i] - prevSmaller[i] - 1;
            best = Math.max(best, heights[i] * width);
        }
        return best;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        prev_smaller = [0] * n
        next_smaller = [0] * n
        st: List[int] = []   # indices; their heights increase bottom -> top

        # Pass 1: for each bar, the nearest bar on the LEFT that is shorter (-1 if none).
        for i in range(n):
            # Bars at least as tall as heights[i] can't stop anyone to the right of i.
            while st and heights[st[-1]] >= heights[i]:
                st.pop()
            prev_smaller[i] = -1 if not st else st[-1]
            st.append(i)

        st.clear()
        # Pass 2: for each bar, the nearest bar on the RIGHT that is shorter (n if none).
        for i in range(n - 1, -1, -1):
            while st and heights[st[-1]] >= heights[i]:
                st.pop()
            next_smaller[i] = n if not st else st[-1]
            st.append(i)

        # Pass 3: bar i is the shortest bar of the rectangle strictly between those two walls.
        best = 0
        for i in range(n):
            width = next_smaller[i] - prev_smaller[i] - 1
            best = max(best, heights[i] * width)

        return best

export function largestRectangleArea(heights: number[]): number {
    const n = heights.length;
    const prevSmaller = new Array(n);
    const nextSmaller = new Array(n);
    const st: number[] = [];   // indices; their heights increase bottom -> top

    // Pass 1: for each bar, the nearest bar on the LEFT that is shorter (-1 if none).
    for (let i = 0; i < n; i++) {
        // Bars at least as tall as heights[i] can't stop anyone to the right of i.
        while (st.length > 0 && heights[st[st.length - 1]] >= heights[i]) {
            st.pop();
        }
        prevSmaller[i] = st.length === 0 ? -1 : st[st.length - 1];
        st.push(i);
    }

    st.length = 0;
    // Pass 2: for each bar, the nearest bar on the RIGHT that is shorter (n if none).
    for (let i = n - 1; i >= 0; i--) {
        while (st.length > 0 && heights[st[st.length - 1]] >= heights[i]) {
            st.pop();
        }
        nextSmaller[i] = st.length === 0 ? n : st[st.length - 1];
        st.push(i);
    }

    // Pass 3: bar i is the shortest bar of the rectangle strictly between those two walls.
    let best = 0;
    for (let i = 0; i < n; i++) {
        const width = nextSmaller[i] - prevSmaller[i] - 1;
        best = Math.max(best, heights[i] * width);
    }
    return best;
}

Complexity

Time O(N)Space O(N)

Three passes and two extra arrays. It is already fast enough; the optimal does the same work in one pass.

Optimized approach

Idea

Start from brute force

The brute force checks every range [left … right] and its minimum height. That is about n²/2 rectangles.

Find the repeated work

For a given shortest bar, only the widest rectangle with that bar as the minimum can win. All narrower ranges with the same minimum are wasted work. So only n rectangles matter, one per bar, and each needs just its two walls.

Define the state — what variables do I need?

st: vector<int> used as a stack of indices. Their heights increase from bottom to top. Each one is a bar still waiting for its right wall.
i: The bar being read now. For i = n it is a fake bar of height 0.
left: After a pop: the new top (the nearest shorter bar on the left), or −1 if the stack is empty.
best: Largest area found so far.

Define validity

The heights on the stack always increase from bottom to top. So the bar just under any bar is the nearest bar to its left that is shorter: its left wall.

Define the transitions — when does each pointer move, and why is it safe?

h(i) ≤ height of the top

Pop the top j. left = new top (or −1). area = heights[j] × (i − left − 1)

Bar i is not taller, so i is j's right wall. Everything strictly between left and i is at least as tall as heights[j] (taller bars were popped earlier, or are still above j), so the full width fits.

h(i) > height of the top (or the stack is empty)

Push i

Bar i doesn't block the top, so the top keeps waiting. The stack stays increasing.

i = n

Use height 0

Every real bar is ≥ 0, so the fake bar pops everything still waiting. Their right wall is the end of the array.

What does the current window add to the answer?

When bar j is popped, it gives the widest rectangle in which it is the shortest bar: heights[j] × (i − left − 1). The best rectangle overall is one of these n candidates.

Code & Implementation

optimal.cpp

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> st;   // indices; their heights increase bottom -> top
        int best = 0;

        // i == n is a fake bar of height 0. It is shorter than everything,
        // so it pops (and finishes) every bar still on the stack.
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!st.empty() && heights[st.back()] >= h) {
                int height = heights[st.back()];
                st.pop_back();
                // Right wall: i (the first shorter bar on the right).
                // Left wall: the bar now on top (shorter than the popped one), or -1 if none.
                int left = st.empty() ? -1 : st.back();
                int width = i - left - 1;
                best = max(best, height * width);
            }
            st.push_back(i);
        }
        return best;
    }
};

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> st = new ArrayDeque<>();   // indices; their heights increase bottom -> top
        int best = 0;

        // i == n is a fake bar of height 0. It is shorter than everything,
        // so it pops (and finishes) every bar still on the stack.
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!st.isEmpty() && heights[st.peek()] >= h) {
                int height = heights[st.pop()];
                // Right wall: i (the first shorter bar on the right).
                // Left wall: the bar now on top (shorter than the popped one), or -1 if none.
                int left = st.isEmpty() ? -1 : st.peek();
                int width = i - left - 1;
                best = Math.max(best, height * width);
            }
            st.push(i);
        }
        return best;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        st: List[int] = []   # indices; their heights increase bottom -> top
        best = 0

        # i == n is a fake bar of height 0. It is shorter than everything,
        # so it pops (and finishes) every bar still on the stack.
        for i in range(n + 1):
            h = 0 if i == n else heights[i]
            while st and heights[st[-1]] >= h:
                height = heights[st.pop()]
                # Right wall: i (the first shorter bar on the right).
                # Left wall: the bar now on top (shorter than the popped one), or -1 if none.
                left = -1 if not st else st[-1]
                width = i - left - 1
                best = max(best, height * width)
            st.append(i)

        return best

export function largestRectangleArea(heights: number[]): number {
    const n = heights.length;
    const st: number[] = [];   // indices; their heights increase bottom -> top
    let best = 0;

    // i == n is a fake bar of height 0. It is shorter than everything,
    // so it pops (and finishes) every bar still on the stack.
    for (let i = 0; i <= n; i++) {
        const h = (i === n) ? 0 : heights[i];
        while (st.length > 0 && heights[st[st.length - 1]] >= h) {
            const height = heights[st.pop()!];
            // Right wall: i (the first shorter bar on the right).
            // Left wall: the bar now on top (shorter than the popped one), or -1 if none.
            const left = st.length === 0 ? -1 : st[st.length - 1];
            const width = i - left - 1;
            best = Math.max(best, height * width);
        }
        st.push(i);
    }
    return best;
}

Complexity

Time O(N)Space O(N)

Each index is pushed once and popped once, so the inner while runs at most n + 1 times in total.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Fix the left edge, extend right, keep the minimum height so far	O(N²)	O(1)
Better	Two stack passes find each bar's walls; a third pass computes the areas	O(N)	O(N)
Optimal	Pop a bar when a shorter one arrives; the arrival is its right wall, the new top is its left wall	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“largest rectangle”The height of a rectangle is the minimum bar it covers → think about each bar as the minimum.
“bars side by side”A contiguous range. Each bar's range is limited by the nearest shorter bar on each side.
“up to 10^5 bars”O(n²) is too slow. We need each bar's walls in O(1) amortized → monotonic stack.

Each element as the minimum+stretch to previous smaller and next smaller+value × width→Monotonic Stack (contribution / boundaries)

This is the anchor of the contribution sub-pattern: for each element, find how far it stretches as the minimum. Here we take the max of height × width, so ties don't change the answer. In Sum of Subarray Minimums we add up every element's share, and then the tie rule decides whether a subarray is counted once or twice.

Don't make this mistake

Using the popped bar's own index as the left edge

✗ int width = i - j; // j = index that was just popped

✓ int left = st.empty() ? -1 : st.back(); int width = i - left - 1;

Taller bars to the left of j were popped earlier, but they still belong to j's rectangle. The left wall is the bar under j on the stack. In [2, 1, 5, 6, 2, 3], bar 1 is popped at the end with an empty stack: its width is 6 (all bars), not 5.

Wrong width when the stack becomes empty

✗ int width = i - st.back() - 1; // st may be empty now

✓ int width = st.empty() ? i : i - st.back() - 1;

An empty stack after the pop means no bar on the left is shorter. The rectangle reaches index 0, so the width is i. Reading st.back() on an empty vector is undefined behaviour.

Forgetting the final flush

✗ for (int i = 0; i < n; i++) { ... } // no sentinel, no cleanup

✓ for (int i = 0; i <= n; i++) { int h = (i == n) ? 0 : heights[i]; ... }

Bars with no shorter bar to their right are never popped inside the loop. For [1, 2, 3, 4, 5] nothing is popped at all and the answer would be 0 instead of 9. The height-0 bar at i = n pops them with right wall n.

Not knowing why int is safe here

The biggest area is at most n × max height = 10^5 × 10^4 = 10^9, which fits in an int (limit about 2.1·10^9). So int is fine. If the limits were bigger (say heights up to 10^9), you would need long long for height * width.

Using two pointers like Container With Most Water

Pattern-confusion trap. In Container With Most Water the water level depends only on the two end lines, so moving the shorter end inward is safe. Here every bar inside the rectangle limits its height, so the minimum of the whole range matters and moving an end pointer can skip the answer. Use each bar as the minimum and find its walls with a stack.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Sum of Subarray Minimums