Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Largest rectangle in a histogram

Hard TUF ID 959 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array heights describing a histogram: bar i has width 1 and height heights[i], and the bars stand next to each other. Return the area of the largest rectangle that fits entirely inside the histogram.

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ heights[i] ≤ 10^4. The largest possible area is 10^4 × 10^5 = 10^9, which still fits in an int.

Example 1

heights = [2, 1, 5, 6, 2, 3]
answer  = 10        // bars 5 and 6 together: height 5, width 2

Example 2

heights = [2, 4]
answer  = 4         // either bar 4 alone, or height 2 across both bars

The key observation. Look at any rectangle inside the histogram. It spans a range of bars l..r, and its height can be at most the shortest bar in that range. So the best rectangle on l..r has area min(heights[l..r]) × (r - l + 1). Equivalently, the optimal rectangle’s height is the height of some bar i, and once we fix that bar we should stretch the rectangle left and right as far as possible, stopping only at a bar shorter than heights[i].

Approach 1: Brute force

Intuition. Enumerate every range l..r. If we fix l and move r to the right one step at a time, the minimum of the range can be updated in O(1), so each range costs constant time.

Algorithm.

1. For every left edge i, set minH to infinity.
2. For every right edge j ≥ i: minH = min(minH, heights[j]), and update the answer with minH × (j - i + 1).

static int bruteForce(int[] heights) {
    int n = heights.length, best = 0;
    for (int i = 0; i < n; i++) {
        int minH = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            minH = Math.min(minH, heights[j]);
            best = Math.max(best, minH * (j - i + 1));
        }
    }
    return best;
}

Complexity. Time O(n^2): one constant-time step per range. Space O(1). For n = 10^5 that is 5 × 10^9 steps, too slow.

Approach 2: Better, previous and next smaller element

Intuition. Turn the key observation into a formula. For bar i, let left[i] be the index of the nearest bar to the left that is strictly shorter, or -1 if there is none, and right[i] the nearest strictly shorter bar to the right, or n. Every bar strictly between them is at least heights[i] tall, so the widest rectangle of height heights[i] covers exactly the bars left[i] + 1 .. right[i] - 1:

area(i) = heights[i] × (right[i] - left[i] - 1)

The answer is the maximum of area(i) over all i, because the optimal rectangle is one of these n candidates.

Computing left[] is the previous smaller element problem. Sweep from left to right with a stack of indices. Before handling bar i, pop every index whose bar is at least as tall as bar i: those bars can never be “the nearest shorter bar” for i or for anything to the right of i, because bar i is closer and no taller. Whatever remains on top is the nearest strictly shorter bar. The right[] array is the same sweep from the right.

Algorithm.

1. Left to right: pop while heights[top] ≥ heights[i]; left[i] = top (or -1); push i.
2. Right to left: same popping rule; right[i] = top (or n); push i.
3. Return the maximum of heights[i] × (right[i] - left[i] - 1).

static int better(int[] heights) {
    int n = heights.length;
    int[] left = new int[n], right = new int[n];   // nearest strictly smaller bar on each side
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && heights[st.peek()] >= heights[i]) st.pop();
        left[i] = st.isEmpty() ? -1 : st.peek();
        st.push(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && heights[st.peek()] >= heights[i]) st.pop();
        right[i] = st.isEmpty() ? n : st.peek();
        st.push(i);
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, heights[i] * (right[i] - left[i] - 1));
    return best;
}

Complexity. Time O(n): in each sweep every index is pushed once and popped at most once. Space O(n) for the two arrays and the stack.

Approach 3: Optimal, a single stack pass

Intuition. We can get both boundaries in one sweep. Keep a stack of indices whose heights are increasing from bottom to top. When bar i arrives and is not taller than the bar on top, the top bar has just found its right boundary: bar i is the first bar to its right that is not taller. Its left boundary is already sitting directly below it in the stack, because the stack is increasing and everything taller that used to sit in between has been popped. So we pop the top and compute its rectangle immediately.

After the last bar, some indices are still on the stack (they never met a shorter bar). Pretending there is an extra bar of height 0 at index n pops all of them with right boundary n.

What about equal heights? The loop pops when heights[top] ≥ h, so for a run of equal bars the earlier ones are popped by the later ones and compute a rectangle that is too narrow. That is harmless: the last bar of the run is popped later by a genuinely shorter bar, and by then the element below it is the true previous shorter bar, so it computes the full width. Under-estimating some candidates never hurts as long as the best one is measured correctly.

Algorithm.

1. For i = 0 .. n (one step past the end), let h = heights[i], or 0 when i == n.
2. While the stack is not empty and heights[top] ≥ h:
   • pop top; leftBoundary is the new top, or -1;
   • update the answer with heights[top] × (i - leftBoundary - 1).
3. Push i.

static int optimal(int[] heights) {
    int n = heights.length, best = 0;
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];       // a height-0 sentinel flushes the stack at the end
        while (!st.isEmpty() && heights[st.peek()] >= h) {
            int height = heights[st.pop()];
            int leftBoundary = st.isEmpty() ? -1 : st.peek();
            best = Math.max(best, height * (i - leftBoundary - 1));
        }
        st.push(i);
    }
    return best;
}

Dry run on heights = [2, 1, 5, 6, 2, 3]:

At i = 4, bar 5 (index 2) is popped with the stack top below it being index 1, so its width is 4 - 1 - 1 = 2: it covers indices 2 and 3, giving area 10.

Complexity. Time O(n): each index is pushed once and popped once. Space O(n) for the stack (an increasing histogram keeps every index on it).

Edge cases and pitfalls

• Strictly increasing or decreasing heights. [1, 2, 3, 4, 5] and its reverse both give 9 (height 3, width 3). In the increasing case nothing is popped until the sentinel; forgetting the sentinel returns 0.
• Equal heights. [1, 1, 1, 1] must return 4. In Approach 2 both sweeps pop on ≥, so both boundaries are strictly shorter bars and every width is exact. In Approach 3 the “last bar of the run is measured correctly” argument covers it. Popping only on > in both sweeps would stop every bar at its equal neighbours and return 1 here. Changing just one sweep is still correct, because one bar of each equal run keeps its full width.
• Zero heights. [0, 0] returns 0. A zero bar splits the histogram into independent parts.
• Empty or single bar. An empty array returns 0; [5] returns 5.
• Overflow. With the stated limits the area is at most 10^9. If heights could reach 10^9 as well, compute the area as long.
• The sentinel index. The loop runs to i == n, but heights[n] is never read: the sentinel height is substituted, and only indices below n are ever popped.

Related problems

• Maximum Rectangles turns every row of a binary matrix into a histogram and calls this solution.
• Next Smaller Element is the stack primitive behind Approach 2.
• Sum of Subarray Ranges uses the same “how far can this element extend” boundaries to count subarrays.
• Trapping Rainwater is another histogram problem with a monotonic-stack solution.