SyntaxPilot
Courses/DSA and Coding Problems/Lesson 28
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 28 of 90

Largest rectangle in a histogram (hard)

queued

These are the notes for DSA episode 28, one of the most famous hard stack problems. Given the heights of bars that stand side by side, find the largest rectangle that fits inside them. The obvious way gives every bar its own rectangle and stretches it left and right: on 2 lakh equal bars that is O(n²) and it times out. The fix: a bar's rectangle stops at its previous smaller and next smaller bar, and a monotonic stack (episode 27) finds both for every bar in one pass. With a sentinel bar of height 0 at the end, the whole solution is O(n) time, O(n) space. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A shop owners' association wants to paste one rectangular banner (a hoarding) across the fronts of a row of shops. Every shop is the same width; their heights are 2, 1, 5, 6, 2 and 3 floors. The banner must cover shops that stand next to each other, and it can't be taller than the shortest shop it covers, or part of it would hang in the air. The biggest banner goes over the shops of height 5 and 6: 5 floors × 2 shops = 10.

On the street In the code
A shop of height h A bar h[i] of width 1
The row of shops The histogram (the heights array)
One banner over neighbouring shops A rectangle over a range of bars [l, r]
The banner's height The shortest bar in the range
The first shorter shop on each side The previous smaller and next smaller bar (the "walls")

Problem statement

Given an array heights where each bar has width 1, return the area of the largest rectangle in the histogram.

heights = [2, 1, 5, 6, 2, 3]   →   10   (bars 5 and 6, at height 5)
heights = [2, 4]               →   4

A rectangle over bars l..r has height min(h[l..r]) and width r - l + 1.

Edge cases: one bar ([5] → 5), all equal ([3, 3, 3, 3] → 12), increasing ([1, 2, 3, 4, 5] → 9), decreasing ([5, 4, 3, 2, 1] → 9). Constraints are usually up to 10⁵ bars, so O(n²) is too slow.

Brute force: give every bar its own banner

The best rectangle has some shortest bar in it. So try every bar i as the shortest: its rectangle is h[i] tall, and it stretches left and right while the neighbours are at least as tall.

    static int brute(int[] h) {
        int n = h.length, best = 0;
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l > 0 && h[l - 1] >= h[i]) l--;
            while (r < n - 1 && h[r + 1] >= h[i]) r++;
            best = Math.max(best, h[i] * (r - l + 1));
        }
        return best;
    }

On the two examples it printed 10 and 4. Correct.

The big input: 2 lakh bars

200000 bars, all of height 1 (Arrays.fill(h, 1)): Time Limit Exceeded.

Why the brute force fails

When all bars are equal, every bar stretches across the whole street: n steps for each of n bars, O(n²).

Bars Steps (about n²)
1,000 10 lakh
20,000 40 crore
2,00,000 4 × 10¹⁰: TLE

Each bar re-walks the street to learn what its neighbour just learned. But look at where each walk stops: on the left at the first shorter bar (the previous smaller bar) and on the right at the first shorter bar (the next smaller bar). Finding the next smaller or next greater element for every position in one pass is exactly what the monotonic stack did in episode 27.

The key insight: a shorter bar finishes every taller bar

Keep a stack of indices whose heights increase from bottom to top (a monotonic stack). Walk the bars left to right:

  1. While bars get taller, push them: nobody's rectangle has ended yet.
  2. When bar i is shorter than (or equal to) the bar on top, bar i is the top's next smaller bar: the top's rectangle can't go past here. Pop it and finish its rectangle now.
  3. After popping, the new top is shorter than the popped bar: it is the popped bar's previous smaller bar, its left wall. If the stack is empty, there is no wall: use -1.
  4. The rectangle sits strictly between the two walls: width = i - left - 1, area = height × width.
  5. Sentinel: bars still in the stack at the end never met a shorter bar. Pretend there is one more bar of height 0 at index n. It is shorter than everything, so it pops (and measures) every remaining bar.

Popping on >= (not just >) is fine: an equal bar's rectangle is measured later by the last of the equal bars, which reaches further left.

Dry run on [2, 1, 5, 6, 2, 3] with the sentinel 0 at index 6:

i h[i] Pops (height × width) Stack after (indices) best
0 2 none [0] 0
1 1 2 × (1 − (−1) − 1) = 2 [1] 2
2 5 none [1, 2] 2
3 6 none [1, 2, 3] 2
4 2 6 × (4 − 2 − 1) = 6, then 5 × (4 − 1 − 1) = 10 [1, 4] 10
5 3 none [1, 4, 5] 10
6 0 (sentinel) 3 × 1 = 3, 2 × (6 − 1 − 1) = 8, 1 × (6 − (−1) − 1) = 6 [6] 10

Every index is pushed once and popped once.

The optimal solution in Java

import java.util.*;

public class Main {
    static int largest(int[] h) {
        Deque<Integer> st = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i <= h.length; i++) {
            int cur = (i == h.length) ? 0 : h[i];
            while (!st.isEmpty() && h[st.peek()] >= cur) {
                int height = h[st.pop()];
                int left = st.isEmpty() ? -1 : st.peek();
                int width = i - left - 1;
                best = Math.max(best, height * width);
            }
            st.push(i);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(largest(new int[]{2, 1, 5, 6, 2, 3}));
        System.out.println(largest(new int[]{2, 4}));
        System.out.println(largest(new int[]{5}));
        System.out.println(largest(new int[]{3, 3, 3, 3}));
        System.out.println(largest(new int[]{1, 2, 3, 4, 5}));
        System.out.println(largest(new int[]{5, 4, 3, 2, 1}));
    }
}

Output:

10
4
5
12
9
9

ArrayDeque used with push, pop and peek is Java's recommended stack (faster than the old Stack class). On the 2 lakh bars of height 1 it printed area 200000 in a few milliseconds (34 ms in our run).

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

long long largest(const vector<int>& h) {
    stack<int> st;
    long long best = 0;
    int n = h.size();
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : h[i];
        while (!st.empty() && h[st.top()] >= cur) {
            int height = h[st.top()]; st.pop();
            int left = st.empty() ? -1 : st.top();
            best = max(best, (long long)height * (i - left - 1));
        }
        st.push(i);
    }
    return best;
}

int main() {
    vector<vector<int>> tests = {{2, 1, 5, 6, 2, 3}, {2, 4}, {5}, {3, 3, 3, 3}, {1, 2, 3, 4, 5}, {5, 4, 3, 2, 1}};
    for (auto& t : tests) cout << largest(t) << "\n";
}

Output: the same six lines as Java. In C++ st.pop() returns nothing, so read st.top() first. The long long avoids overflow (bug 3 below).

The same solution in Python

def largest(h):
    st = []                      # indices, heights increasing
    best = 0
    n = len(h)
    for i in range(n + 1):
        cur = 0 if i == n else h[i]   # sentinel 0 at the end
        while st and h[st[-1]] >= cur:
            height = h[st.pop()]
            left = st[-1] if st else -1
            best = max(best, height * (i - left - 1))
        st.append(i)
    return best

for t in ([2, 1, 5, 6, 2, 3], [2, 4], [5], [3, 3, 3, 3], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1]):
    print(largest(t))

Output: the same six lines as Java. A Python list is the stack (append / pop / [-1]), and Python integers never overflow.

Three real bugs

Bug 1: no sentinel (i < h.length)

The loop stops at the last bar. On the example it still printed 10 (by luck: bar 2 at index 4 popped the 6 and the 5), but on [1, 2, 3, 4, 5] it printed 0: increasing bars are never popped, so their rectangles are never measured. Fix: loop to i <= h.length with cur = 0 at the end.

Bug 2: width = i - left

On the example it printed 15 instead of 10: when height 5 was popped, it got width 3 and "covered" the bar of height 1. Both i and left are walls (shorter bars the rectangle can't include), so width = i - left - 1.

Bug 3: int overflow when heights are huge

100000 bars of height 50000: the real answer is 5,000,000,000, but height * width overflows int (max 2,147,483,647) and the program printed 2147450000. On LeetCode 84 (heights ≤ 10⁴, n ≤ 10⁵) int is enough; when a problem allows bigger values, use long best and (long) height * width.

Also seen: int left = st.peek(); without the empty check throws

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Deque.peek()" is null

because peek() on an empty ArrayDeque returns null, and unboxing null into an int fails.

Complexity

Approach Time Extra space 2 lakh bars of height 1
All pairs (l, r) with a running minimum O(n²) O(1) Time Limit Exceeded
Stretch every bar left and right O(n²) worst case O(1) Time Limit Exceeded
Divide and conquer on the minimum O(n log n) average, O(n²) sorted input O(log n) to O(n) risky
prevSmaller[] + nextSmaller[] arrays O(n) O(n) fast
One-pass monotonic stack + sentinel O(n) O(n) milliseconds

The while loop looks nested, but every index is pushed once and popped at most once, so the total work is about 2n.

Common mistakes

Mistake What you see Why Fix
i < h.length (no sentinel) 0 for [1, 2, 3, 4, 5] bars left in the stack are never measured loop to i <= n with height 0
width = i - left 15 instead of 10 both walls are outside the rectangle width = i - left - 1
int best, height * width with huge heights 2147450000, not 5000000000 int overflows past 2.1 billion long best, (long) height * width
left = st.peek() on an empty stack NullPointerException ... peek() is null empty ArrayDeque.peek() returns null st.isEmpty() ? -1 : st.peek()
Pushing heights instead of indices wrong widths you need positions to measure width push i, read h[i]
Stretching every bar TLE on 2 lakh bars O(n²) monotonic stack

Mini project: the biggest hoarding on your street

Write the heights of the shops on a street in an array and print the best banner: its area and which shops it covers. Track the left and right index whenever best improves: when a popped bar gives a bigger area, the banner covers shops left + 1 to i - 1. For {3, 7, 7, 8, 2, 6, 6, 5, 1} the program prints [21, 1, 3]: area 21, shops 1 to 3 at height 7. Extension: also print the banner's height, and draw the street with # characters.

Practice

  1. Maximal rectangle of 1s in a binary matrix (LeetCode 85).
Solution

Each row is the floor of a histogram: h[j] = number of consecutive 1s ending at this row in column j. Run largest on every row.

    static int maximalRectangle(char[][] m) {
        if (m.length == 0) return 0;
        int[] h = new int[m[0].length];
        int best = 0;
        for (char[] row : m) {
            for (int j = 0; j < row.length; j++) h[j] = row[j] == '1' ? h[j] + 1 : 0;
            best = Math.max(best, largest(h));
        }
        return best;
    }

For the matrix 10100 / 10111 / 11111 / 10010 it prints 6. O(rows × cols).

  1. Write it with two arrays: prevSmaller[] and nextSmaller[].
Solution

Two monotonic-stack passes (episode 27), one from each side; the width is next[i] - prev[i] - 1.

    static int twoArrays(int[] h) {
        int n = h.length;
        int[] prev = new int[n], next = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && h[st.peek()] >= h[i]) st.pop();
            prev[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && h[st.peek()] >= h[i]) st.pop();
            next[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }
        int best = 0;
        for (int i = 0; i < n; i++) best = Math.max(best, h[i] * (next[i] - prev[i] - 1));
        return best;
    }

[2, 1, 5, 6, 2, 3] → 10.

  1. Return the left and right index of the best rectangle.
Solution
    static int[] where(int[] h) {
        Deque<Integer> st = new ArrayDeque<>();
        int best = 0, bl = 0, br = -1;
        for (int i = 0; i <= h.length; i++) {
            int cur = (i == h.length) ? 0 : h[i];
            while (!st.isEmpty() && h[st.peek()] >= cur) {
                int height = h[st.pop()];
                int left = st.isEmpty() ? -1 : st.peek();
                if (height * (i - left - 1) > best) { best = height * (i - left - 1); bl = left + 1; br = i - 1; }
            }
            st.push(i);
        }
        return new int[]{best, bl, br};
    }

[2, 1, 5, 6, 2, 3] → [10, 2, 3].

  1. Largest square instead of rectangle.
Solution

When a bar is popped, its rectangle is height tall and width wide; the biggest square inside it has side min(height, width).

                int side = Math.min(height, i - left - 1);
                best = Math.max(best, side * side);

[2, 1, 5, 6, 2, 3] → 4; [4, 4, 4, 4, 1] → 16.

Quick quiz

System.out.println(largest(new int[]{4, 2, 0, 3, 2, 5}));
  • 5
  • 6
  • 8
  • 4
Answer

6. The 0 splits the street. On the right, bars 3, 2, 5 (indices 3 to 5) at height 2 give 2 × 3 = 6, which beats the single 5. On the left, 4 and 2 give at most 4. (Real output: 6.)

Interview questions

  1. Largest rectangle in a histogram in O(n). Monotonic stack of indices with increasing heights; a shorter bar pops the taller ones; for each popped bar, width = i - newTop - 1 (or i if the stack is empty); a sentinel 0 at the end flushes the stack.
  2. Why is it O(n) when there's a loop inside a loop? Each index is pushed once and popped at most once: at most 2n stack operations in total (amortised analysis).
  3. Why push indices and not heights? The width needs positions; the height can always be read back from h[index].
  4. What does the sentinel do? It is a fake bar of height 0 after the end; it is shorter than every bar, so every remaining index gets popped and measured.
  5. >= or > when popping? Both give the right answer. With >=, the earlier of two equal bars is measured short, but the later one covers the full width.
  6. How do you solve "maximal rectangle" in a 0/1 matrix? Build a histogram per row (consecutive 1s above each cell) and run this algorithm on every row.
  7. How is this related to "next greater element"? It is the same stack pattern looking for the next smaller element, plus reading the previous smaller element from the stack below.
  8. When does the answer overflow int? When max height × n exceeds about 2.1 × 10⁹; use long.

Glossary

Term Meaning
Histogram A bar chart whose bars have width 1 and stand side by side with no gaps
Rectangle in a histogram A range of neighbouring bars [l, r], as tall as its shortest bar
Previous smaller bar The nearest bar to the left that is shorter: the rectangle's left wall
Next smaller bar The nearest bar to the right that is shorter: the rectangle's right wall
Stack A pile where you add (push) and remove (pop) only at the top: last in, first out
Monotonic stack A stack whose values stay sorted (here: heights increasing from bottom to top)
Sentinel A fake value added at the end (height 0) to force a final clean-up
ArrayDeque Java's double-ended queue; with push / pop / peek it is the recommended stack
peek() Look at the top of the stack without removing it (null if empty, in ArrayDeque)
Amortised O(n) The total work over the whole run is O(n), even if one step does more
Integer overflow A result bigger than the type can hold wraps around to a wrong number
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • A rectangle's height is its shortest bar; stretching every bar left and right is O(n²) and times out on 2 lakh bars.
  • Every bar's rectangle ends at its previous smaller and next smaller bar. A monotonic stack (increasing heights) finds both: a shorter bar pops the taller ones, the new top is the left wall, width = i - left - 1.
  • A sentinel height 0 at index n flushes the stack. O(n) time, O(n) space; use long when heights are huge.

Next episode: Min stack and evaluating reverse Polish notation.