Limited Time Offer:Up to 20% off Hello Interview Premium

⌘K

Tutor

Stack

Largest Rectangle in Histogram

hard

DESCRIPTION (inspired by Leetcode.com)

Given an integer array heights representing the heights of histogram bars, write a function to find the largest rectangular area possible in a histogram, where each bar's width is 1.

Inputs:

heights = [2,8,5,6,2,3]

Output:

Explanation

To solve this question, we calculate the largest rectangle that contains the bar at each index of the array, and return the largest of those rectangles at the end. By using a monotonically increasing stack, we can solve this question in O(n) time complexity, compared to the brute-force solution which takes O(n²) time.

Largest Rectangle at each Index

To calculate the largest rectangle at each index, we need to know the index of the first shorter bar to both the left and the right of the current bar. The width of the rectangle is the difference between the two indices - 1, and the height is the height of the current bar.

Index of first shorter bar to left: 0. Index of first shorter bar to right: 2. Total area: 8 * (2 - 0 - 1) = 8

Index of first shorter bar to left: 0. Index of first shorter bar to right: 4. Total area: 5 * (4 - 0 - 1) = 15

Brute-Force Solution

The brute-force solution iterates over each bar in the array, and for each bar, finds the first shortest bar to the left and the right of the bar using two while loops, for a time complexity of O(n²).

Solution

def largestRectangleArea(heights):
    max_area = 0
    n = len(heights)
    for i in range(n): 
        left = i - 1
        while left >= 0 and heights[left] >= heights[i]:
            left -= 1
        right = i + 1
        while right < n and heights[right] >= heights[i]:
            right += 1
        max_area = max(max_area, (right - left - 1) * heights[i])
    
    return max_area

Monotonically Increasing Stack

By using a monotonically increasing stack, we can find the first shortest bar to the left and right of each bar in O(n) time complexity.

We first initialize our stack, as well as a variable to store the maximum area and a pointer i to iterate over the array. The stack contains the indices of the bars in increasing order of their heights. When an index is placed on the stack, it means we are waiting to find a shorter bar to the right of that current index.

Visualization


def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)
  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

largest rectangle in histogram

0 / 1

We then iterate over the array. If height[i] is greater than the height of the index at the top of the stack, we push i onto the stack. If i is less than the height of index at the top of the stack, we pop the index at the top of the stack and calculate the area of the rectangle containing that index.

Pushing to the Stack

If height[i] is greater than the height of the index at the top of the stack (or if the stack is currently empty), we push i onto the stack. This means we are waiting to find a shorter bar to the right of i, and we increment i.

Visualization


def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)
  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

initialize variables

0 / 2

Pushing `i = 0` and `i = 1` to the stack

Popping from the Stack

If height[i] is less than the height of the index at the top of the stack, we have enough information to calculate the area of the rectangle containing the index at the top of the stack. i is the first shorter bar to the right of the index at the top of the stack. Because the stack is monotonically increasing, the index beneath the index at the top is the first shorter bar to the left of it (or -1 if the stack is empty).

Visualization


def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)
  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

push to stack

0 / 1

At this point, i = 2, and the top of the stack is 1. heights[2] < heights[1] (5 < 8), so i is the right boundary for the rectangle at index 1. The left boundary is the index at the top of the stack after popping 1 from the stack (in this case, 0).

i still has the potential to be the right boundary for the new index at the top of the stack after the previous index was popped, so we don't increment i, and instead, move to the next iteration.

Visualization


def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)
  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

push to stack

0 / 2

Another example. `i = 4`, and is the right boundary for both indexes 3 and 2.

Emptying the Stack

When i has iterated over the entire array, we still need to process the remaining indexes on the stack, which are the indexes that have not yet found a shorter bar to the right. So to calculate the area of the rectangle for these indexes, we use the end of the array as the right boundary, while the calculation for the left boundary remains the same.

When the stack is empty, we have processed all the indexes, and we return the maximum area.

Visualization


def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)
  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

push to stack

0 / 4

Emptying the stack, and returning `maxArea`.

Solution

Visualization

Try these examples:


def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)
  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

largest rectangle in histogram

0 / 14

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) where n is the length of the input array. Each item is pushed and popped from the stack at most once.

Space Complexity: O(n) where n is the length of the input array for the size of the stack.

Mark as read

Next: Linked List Overview

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations

Guided Practice

Recent interview questions

Learn More

Reading Progress

On This Page

Explanation

Solution

Stack

Largest Rectangle in Histogram

DESCRIPTION (inspired by Leetcode.com)

Explanation

Largest Rectangle at each Index

Brute-Force Solution

Monotonically Increasing Stack

Pushing to the Stack

Popping from the Stack

Emptying the Stack

Solution

Test Your Knowledge

Complexity Analysis

Comments

Questions

Learn

Links

Legal

Contact