Get Premium
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:

15

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(n2) 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.
285623;012345
Index of first shorter bar to left: 0. Index of first shorter bar to right: 2. Total area: 8 * (2 - 0 - 1) = 8
285623;012345
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 shorter bar to the left and the right of the bar using two while loops, for a time complexity of O(n2).
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 shorter 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
285623;012345

largest rectangle in histogram

0 / 1

We then iterate over the array. If heights[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 heights[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
285623;012345imaxArea: 0stack

initialize variables

0 / 2

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

Popping from the Stack

If heights[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
285623;012345imaxArea: 001stack

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
285623;012345imaxArea: 8023stack

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
285623;012345imaxArea: 15045stack

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
285623;012345

largest rectangle in histogram

0 / 14

Test Your Knowledge

Login to take the complexity quiz and track your progress

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.

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsAnthropic SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift PremiumHello Interview Premium
Legal
Terms and ConditionsPrivacy PolicySecurity
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.

Largest Rectangle in Histogram | Hello Interview