Largest Rectangle in Histogram

Published at23 Jul 2026

Stack Hard 0 views

Like0

You are given an array of integers representing the heights of histogram bars where each bar has width 1. Find the area of the largest rectangle that can be formed within the bounds of the histogram.

The brute force approach checks every possible rectangle by expanding left and right from each bar, running in O(n²). A monotonic increasing stack solves it in O(n). As you iterate through the bars, the stack maintains indices of bars in increasing height order. When a shorter bar arrives, it means the taller bar on the stack cannot extend further to the right. Pop the taller bar, calculate its area using the current index as the right boundary and the new top of stack as the left boundary, and update the maximum.

At the end, process any remaining bars in the stack with the array length as the right boundary.

The monotonic increasing stack is the key to the O(n) solution. The stack maintains indices of bars in increasing height order. When a shorter bar arrives, it means the taller bars in the stack cannot extend further to the right. For each popped bar, its height is the limiting factor, and the width is determined by the distance between the current index and the new top of stack.

A critical part of this algorithm is the sentinel value of 0 at the end. By iterating to heights.length and treating the extra iteration as height 0, all remaining bars in the stack are automatically processed because 0 is shorter than any positive height.

The brute force approach expands left and right from each bar, checking every possible rectangle, which runs in O(n²). The stack approach is O(n) because each index is pushed and popped exactly once.

This is one of the most commonly asked hard-level stack problems in interviews. Understanding the boundary calculation is the hardest part.

The key to understanding this algorithm is realizing that the maximum rectangle containing a particular bar as the shortest bar extends from the previous shorter bar to the next shorter bar. The monotonic stack discovers these boundaries efficiently by keeping indices of bars in increasing height order.

When visualizing this algorithm, imagine each bar being pushed onto the stack, waiting for a shorter bar to its right that will define its right boundary. The left boundary is determined by the bar immediately below it in the stack. This dual-boundary discovery is what makes the algorithm elegant.

Practice tracing through the example [2,1,5,6,2,3] step by step to fully understand how the stack maintains the boundaries and how the maximum area of 10 is found.

Example Input & Output

Example 1

Input

[2,1,5,6,2,3]

Output

Explanation

The largest rectangle is formed by bars of height 2 and 5,6,2 spanning width 2 (area 5x2=10, or the 2x5 rectangle).

Example 2

Input

[1,1,1,1]

Output

Explanation

All bars height 1, width 4, area 4.

Example 3

Input

[2,4]

Output

Explanation

Either the full 2x2 rectangle (area 4) or the 4x1 bar (area 4).

Algorithm Flow

Recommendation Algorithm Flow for Largest Rectangle in Histogram

Solution Approach

Iterate through heights. While the stack is not empty and the current height is less than the height at the top of the stack, pop the top index. The height for that popped bar is its own height. The width is the current index minus the new top index minus 1 (or just the current index if the stack is empty). Calculate area and update the maximum. Push the current index. After the loop, process remaining indices with n as the right boundary.

function solution(heights) {
  var stack = [];
  var maxArea = 0;
  for (var i = 0; i <= heights.length; i++) {
    var h = i < heights.length ? heights[i] : 0;
    while (stack.length && h < heights[stack[stack.length - 1]]) {
      var height = heights[stack.pop()];
      var width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

Time complexity is O(n). Space complexity is O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int solution(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= heights.length; i++) {
            int h = i < heights.length ? heights[i] : 0;
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

javascript

function solution(heights) {
  var stack = [];
  var maxArea = 0;
  for (var i = 0; i <= heights.length; i++) {
    var h = i < heights.length ? heights[i] : 0;
    while (stack.length && h < heights[stack[stack.length - 1]]) {
      var height = heights[stack.pop()];
      var width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

php

<?php
function solution($heights) {
    $stack = []; $maxArea = 0;
    for ($i = 0; $i <= count($heights); $i++) {
        $h = $i < count($heights) ? $heights[$i] : 0;
        while (!empty($stack) && $h < $heights[end($stack)]) {
            $height = $heights[array_pop($stack)];
            $width = empty($stack) ? $i : $i - end($stack) - 1;
            $maxArea = max($maxArea, $height * $width);
        }
        array_push($stack, $i);
    }
    return $maxArea;
}

python

def solution(heights):
    stack = []
    max_area = 0
    for i in range(len(heights) + 1):
        h = heights[i] if i < len(heights) else 0
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1 if stack else i
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

rust

fn solution(heights: Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut max_area = 0;
    for i in 0..=heights.len() {
        let h = if i < heights.len() { heights[i] } else { 0 };
        while let Some(&top) = stack.last() {
            if h >= heights[top] { break; }
            let height = heights[stack.pop().unwrap()];
            let width = if stack.is_empty() { i as i32 } else { (i - *stack.last().unwrap() - 1) as i32 };
            max_area = max_area.max(height * width);
        }
        stack.push(i);
    }
    max_area
}

typescript

function solution(heights: number[]): number {
    var stack: number[] = [];
    var maxArea = 0;
    for (var i = 0; i <= heights.length; i++) {
        var h = i < heights.length ? heights[i] : 0;
        while (stack.length && h < heights[stack[stack.length - 1]]) {
            var height = heights[stack.pop() as number];
            var width = stack.length ? i - (stack[stack.length - 1] as number) - 1 : i;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Largest Rectangle in Histogram

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Gallery Stock Order Check

Harbor Cargo Lineup

Warehouse Crate Ordering

Festival Drum Echoes

Valid Parentheses Grouping

Next Greater Element

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.