Largest Rectangle in Histogram

DESCRIPTION (credit 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.

EXAMPLES

Inputs:


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

Output:

Run your code to see results here

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²).


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.


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.


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).


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.


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.


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


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

Complexity Analysis

Time Complexity: O(n). 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.

Next: Overview

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

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Daily Temperatures

Linked List: Overview