How do you solve Largest Rectangle in Histogram?

Use a monotonic increasing stack to store pairs of (start index, height). Iterate through the bars, and for each bar, pop from the stack while the current bar is shorter than the top of the stack. For each popped bar, calculate the area using its height and the width determined by the current index and the popped bar's start index. Push the current bar with the updated start index onto the stack. After processing all bars, pop remaining bars and calculate areas considering the histogram's end as the right boundary. This guarantees O(n) time complexity as each bar is pushed and popped once.

What pattern does Largest Rectangle in Histogram use?

The Pattern: Monotonic Stack (Nearest Smaller Elements for Range Queries) The Heuristic: Maintain a stack of bars in increasing height order so that when a shorter bar appears, it signals the end of rectangles for taller bars; popping these bars reveals their maximal width bounded by the current index and the previous smaller bar.

Largest Rectangle in Histogram — Monotonic Stack

Q: What is the time complexity of Largest Rectangle in Histogram?

O(n). Each bar is pushed onto the stack once and popped at most once, resulting in linear time complexity.

Problem

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

1 ≤ heights.length ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Example

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

Output: 10

A brute-force approach would check every possible rectangle by iterating over all pairs of bars and calculating the minimum height in that range, resulting in O(n^2) time complexity. Instead, the algorithm uses a stack to track bars in increasing order of height. When a bar shorter than the top of the stack is encountered, it means the rectangle with the height of the popped bar can no longer extend to the right. The algorithm calculates the area for that bar considering the current index as the right boundary and the index stored in the stack as the left boundary. This process continues until the stack is empty or the current bar is taller than the top of the stack. After processing all bars, the algorithm calculates areas for the remaining bars in the stack considering the histogram's end as the right boundary. This approach efficiently computes the largest rectangle in O(n) time by ensuring each bar is pushed and popped at most once.

Approach

Straightforward Solution

A brute-force approach checks every pair of bars and finds the minimum height in that range to calculate the area, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The largest rectangle for any bar is limited by the first smaller bar to its left and right. By maintaining a stack of bars in increasing height order, the algorithm can efficiently find these boundaries for each bar.

Path to Optimal

Preview

The key recognition signals are 'largest rectangle', 'histogram bars', and 'contiguous bars'. These indicate the Monotonic Stack pattern because the problem requires efficiently finding the nearest smaller elements to the left and right for each bar to determine maximal width…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a monotonic increasing stack to store pairs of (start index, height). Iterate through the bars, and for each bar, pop from the stack while the current bar is shorter than the top of the stack…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each bar is pushed onto the stack once and popped at most once, resulting in linear time complexity.

Space

O(n)

The stack can hold up to n bars in the worst case, requiring O(n) auxiliary space.

Solution

Python

1class Solution:
  def largestRectangleArea(self, heights: list[int]) -> int:
      max_area = 0
      stack = [] 
5
      for i, h in enumerate(heights):
          start = i
          while stack and stack[-1][1] > h:
              index, height = stack.pop()
              max_area = max(max_area, height * (i - index))
              start = index
          stack.append((start, h))
13
      for i, h in stack:
          max_area = max(max_area, h * (len(heights) - i))
16
      return max_area

Step-by-Step Solution

1

Initialize Maximum Area and Monotonic Stack

3max_area = 0
4stack = [] 

Objective

To set up variables for tracking the maximum rectangle area and maintain a stack of bars in increasing height order.

Key Insight

Initializing max_area to zero provides a baseline for comparison. The stack stores tuples of (start index, height) to track bars and their earliest possible start positions, enabling efficient width calculation when bars are popped.

Interview Quick-Check

Core Logic

The stack maintains bars in increasing height order, storing their start indices to calculate widths when popping.

State & Boundaries

max_area starts at zero and updates only when a larger rectangle is found.

2

Process Each Bar and Calculate Areas by Popping Taller Bars

To iterate through each bar, pop taller bars from the stack when a shorter bar is encountered, and calculate the maximal rectangle areas for those popped bars.

3

Calculate Areas for Remaining Bars After Full Iteration

To compute maximal rectangle areas for bars remaining in the stack after processing all histogram bars, considering the histogram's end as the right boundary.

4

Return the Maximum Rectangle Area Found

To return the largest rectangle area computed after processing all bars.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 8 Critical

while stack and stack[-1][1] > h:

While the stack is not empty and the top bar's height is greater than the current bar's height, pop from the stack.

Encountering a shorter bar signals the end of rectangles for taller bars; popping them allows calculation of their maximal rectangle areas bounded by the current index.

Line 10 Critical

max_area = max(max_area, height * (i - index))

Update max_area with the maximum of current max_area and the popped bar's area.

Calculating area as height times width (current index minus popped bar's start index) captures the largest rectangle for that bar ending at the current position.

Line 15 Critical

max_area = max(max_area, h * (len(heights) - i))

Update max_area with the maximum of current max_area and the area of the remaining bars extending to the histogram's end.

Calculating area as height times (histogram length minus start index) ensures all potential maximal rectangles are considered.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does the algorithm pop bars from the stack when encountering a shorter bar, and how does this help compute the largest rectangle?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Largest Rectangle in Histogram from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Largest Rectangle in Histogram drill

or drill a free problem

1	`class Solution:`
2	`def largestRectangleArea(self, heights: list[int]) -> int:`
3	`max_area = 0`
4	`stack = []`
5
6	`for i, h in enumerate(heights):`
7	`start = i`
8	`while stack and stack[-1][1] > h:`
9	`index, height = stack.pop()`
10	`max_area = max(max_area, height * (i - index))`
11	`start = index`
12	`stack.append((start, h))`
13
14	`for i, h in stack:`
15	`max_area = max(max_area, h * (len(heights) - i))`
16
17	`return max_area`