Largest Rectangle in Histogram

Find the maximum area rectangle that can be formed by contiguous bars in a histogram.

Language Selection

Choose your preferred programming language

Showing: Python

Largest Rectangle in Histogram

Problem Statement

You are given an array of non-negative integers heights, where heights[i] is the height of the i-th bar in a histogram. Each bar has width = 1.

Return the area of the largest rectangle that can be formed using contiguous bars.

Examples

Example 1

  • Input: heights = [2,1,5,6,2,3]
  • Output: 10
  • Explanation: The largest rectangle uses bars with heights [5,6] (width 2, height 5) → area 5 * 2 = 10.

Example 2

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

Example 3 (edge case: all zeros)

  • Input: heights = [0,0,0]
  • Output: 0

Example 4 (edge case: single bar)

  • Input: heights = [7]
  • Output: 7

Constraints

  • 1 <= heights.length <= 10^5 (in interviews, you may also be asked to handle empty input)
  • 0 <= heights[i] <= 10^4

Intuition — what insight unlocks the solution?

The key challenge is: for each bar, how far can we extend left and right while keeping the rectangle height at least that bar’s height?

This is a classic Monotonic Stack problem:

  • If we know the previous smaller element and next smaller element for each bar, then that bar is the limiting (minimum) height over a maximal span.
  • A monotonic increasing stack of indices lets us discover those boundaries in one pass.

Pattern: Monotonic Stack (increasing).

Approach

Interviewers usually expect you to start with a correct baseline and then optimize.

Approach 1: Brute force (O(n²))

Try every subarray [L..R], track the minimum height as you expand R, and compute area:

  • For each L, set minH = +∞
  • For R = L..n-1:
    • minH = min(minH, heights[R])
    • area = minH * (R - L + 1)

This is correct but too slow for n = 10^5.

Approach 2 (Optimal): Single-pass monotonic stack (O(n))

Maintain a stack of indices whose heights are non-decreasing.

Invariant: heights[stack[0]] <= heights[stack[1]] <= ...

Process bars from left to right. When you see a bar that is shorter than the bar at the stack top, you’ve found the right boundary for rectangles where the popped bar is the limiting height.

For a popped index top:

  • h = heights[top]
  • Right boundary is i - 1 (current bar i is the first smaller)
  • After popping, the new stack top is the index of the previous smaller bar (leftLess)
  • Width is:
    • If stack is empty: width = i (spans from 0 to i-1)
    • Else: width = i - stackTop - 1
  • Area: h * width

Important detail: flushing the stack If the histogram ends with increasing heights, they never get popped. A common trick is to append a trailing sentinel height 0 to force popping everything.

We also use 64-bit arithmetic (long, long long, etc.) to be safe in non-LeetCode settings.

Solution

Python:

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # Handle interview-style edge case (LeetCode guarantees n >= 1)
        if not heights:
            return 0

        # Append a sentinel 0 to flush the stack at the end
        arr = heights + [0]
        stack: List[int] = []  # stack of indices with non-decreasing heights
        best = 0

        for i, cur_h in enumerate(arr):
            # Pop while the monotonic (increasing) property is violated
            while stack and arr[stack[-1]] > cur_h:
                top = stack.pop()
                h = arr[top]

                # After popping, stack[-1] is index of previous smaller element
                left_less = stack[-1] if stack else -1
                width = i - left_less - 1
                best = max(best, h * width)

            stack.append(i)

        return best

Java:

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;

        int n = heights.length;
        int[] arr = Arrays.copyOf(heights, n + 1);
        arr[n] = 0; // sentinel to flush stack

        Deque<Integer> stack = new ArrayDeque<>(); // indices, heights are non-decreasing
        long best = 0;

        for (int i = 0; i < arr.length; i++) {
            int curH = arr[i];

            while (!stack.isEmpty() && arr[stack.peekLast()] > curH) {
                int top = stack.pollLast();
                long h = arr[top];

                int leftLess = stack.isEmpty() ? -1 : stack.peekLast();
                long width = i - leftLess - 1;
                best = Math.max(best, h * width);
            }

            stack.addLast(i);
        }

        return (int) best;
    }
}

Go:

package main

func largestRectangleArea(heights []int) int {
	if len(heights) == 0 {
		return 0
	}

	// Append sentinel 0
	arr := make([]int, 0, len(heights)+1)
	arr = append(arr, heights...)
	arr = append(arr, 0)

	stack := make([]int, 0) // indices
	var best int64 = 0

	for i := 0; i < len(arr); i++ {
		curH := arr[i]
		for len(stack) > 0 && arr[stack[len(stack)-1]] > curH {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			h := int64(arr[top])

			leftLess := -1
			if len(stack) > 0 {
				leftLess = stack[len(stack)-1]
			}
			width := int64(i - leftLess - 1)
			area := h * width
			if area > best {
				best = area
			}
		}
		stack = append(stack, i)
	}

	return int(best)
}

JavaScript:

/**
 * @param {number[]} heights
 * @return {number}
 */
function largestRectangleArea(heights) {
  if (!heights || heights.length === 0) return 0;

  const arr = heights.concat([0]); // sentinel
  const stack = []; // indices with non-decreasing heights
  let best = 0;

  for (let i = 0; i < arr.length; i++) {
    const curH = arr[i];

    while (stack.length > 0 && arr[stack[stack.length - 1]] > curH) {
      const top = stack.pop();
      const h = arr[top];

      const leftLess = stack.length === 0 ? -1 : stack[stack.length - 1];
      const width = i - leftLess - 1;
      best = Math.max(best, h * width);
    }

    stack.push(i);
  }

  return best;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        if (heights == null || heights.Length == 0) return 0;

        int n = heights.Length;
        int[] arr = new int[n + 1];
        Array.Copy(heights, arr, n);
        arr[n] = 0; // sentinel

        var stack = new List<int>(); // indices, heights are non-decreasing
        long best = 0;

        for (int i = 0; i < arr.Length; i++) {
            int curH = arr[i];

            while (stack.Count > 0 && arr[stack[stack.Count - 1]] > curH) {
                int top = stack[stack.Count - 1];
                stack.RemoveAt(stack.Count - 1);

                long h = arr[top];
                int leftLess = (stack.Count == 0) ? -1 : stack[stack.Count - 1];
                long width = i - leftLess - 1;
                best = Math.Max(best, h * width);
            }

            stack.Add(i);
        }

        return (int)best;
    }
}

Complexity Analysis

Let n = heights.length.

  • Time: O(n) because each index is pushed onto the stack at most once and popped at most once. The total number of stack operations across the loop is linear (amortized analysis).
  • Space: O(n) because in the worst case (strictly increasing heights), the stack can hold all n indices.

Common Mistakes

  1. Wrong width formula after popping

    • After popping top, the rectangle with height heights[top] spans from (stackTop + 1) to (i - 1).
    • Width must be i - stackTop - 1 (or i if the stack is empty).

  2. Forgetting to flush remaining bars

    • If the array ends with increasing heights, you’ll miss rectangles unless you do a final flush.
    • Fix: append a sentinel 0 and run the same logic.

  3. Handling duplicates incorrectly (> vs >=)

    • A safe/common choice is to pop while heights[stackTop] > curHeight (strictly greater).
    • If you use >=, you must be consistent; otherwise you can shrink widths for equal-height plateaus.

  4. Integer overflow in other environments

    • LeetCode’s max area is about 1e9, but interview constraints may be larger.
    • Use 64-bit (long/int64) for area calculations.

Related / Follow-up Problems

  • Maximal Rectangle (2D extension: build histograms row-by-row and reuse this algorithm)
  • Returning the rectangle boundaries (left index, right index, height) instead of just the area
  • Supporting updates to the histogram (often leads to segment trees / RMQ)