Skip to main content
Talentd

Largest Rectangle in Histogram - Solution & Explanation

HardArrayStackMonotonic Stack22 min readAsked at: Amazon, Microsoft, Apple +27
Practice this problem

Problem Statement

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.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104

Approach Overview

Problem Overview: You are given an array where each element represents the height of a histogram bar. The goal is to find the largest rectangular area that can be formed using consecutive bars. The rectangle must use the full width of the selected bars and the minimum height among them.

Approach 1: Divide and Conquer (Average O(n log n), Worst O(nĀ²) time, O(log n) space)

This approach mirrors the strategy used in problems like maximum subarray. For a given range, find the index of the minimum height bar. That bar becomes the limiting height of a rectangle spanning the entire range. Compute three candidates: rectangle using the minimum bar across the full width, best rectangle in the left subarray, and best rectangle in the right subarray. Recursively evaluate both halves and return the maximum. The method is intuitive but can degrade to O(nĀ²) if the array is already sorted because the minimum element repeatedly splits the array unevenly.

Approach 2: Monotonic Stack Method (O(n) time, O(n) space)

This method uses a stack to maintain indices of histogram bars in increasing height order. While iterating through the array, push indices as long as heights keep increasing. When a smaller height appears, repeatedly pop from the stack because the popped bar can no longer extend further right. Calculate the area using the popped height as the smallest bar and the distance between the current index and the new stack top as the width. This stack is called a monotonic stack because heights remain ordered. Each bar is pushed and popped at most once, giving linear time complexity.

Recommended for interviews: The monotonic stack approach is what most interviewers expect. It demonstrates understanding of boundary expansion problems and efficient stack usage. The divide and conquer idea helps build intuition, but the O(n) stack solution shows stronger algorithmic optimization skills.

Approach 1: Monotonic Stack Method

This approach utilizes a monotonic stack to efficiently track the heights of the histogram bars. By iterating through the array and maintaining a stack of indices, we can pop the stack whenever we find a shorter bar, calculate the area of the rectangle formed with the popped bar as the shortest.bar and update the maximum area if necessary. The stack helps to find the left and right boundaries for each bar to compute the area.

The C implementation uses a stack to keep track of histogram bar indices. As we iterate through the height array, when we find a smaller height or the end of the array, we calculate the area of rectangles with heights of bars represented by indices in the stack (as they become the limiting height). As a result, when popping from the stack, we know there cannot be a higher height on the left, hence our width is calculated by i - stack[top] - 1. The maximum rectangle area is then updated accordingly. Finally, the stack is freed to ensure no memory leaks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of bars (height array length), since each bar is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack.

Try this approach in the editor ā†’

Approach 2: Divide and Conquer

This approach is inspired by the algorithm for finding the maximum subarray sum, with the core idea to exploit the properties of minimal elements acting as the constraints. Here, smaller segments of the array are divided to compute maximum rectangular areas separately and then to combine comprehensive results. It works optimally when the heights array is transformed to assist binary division, allowing recursive calls to determine the peak areas between and within divisions.

The C code employs a recursive divide and conquer methodology, recursively finding the minimum height in each segment as a pivot for maximal rectangle widths. It calculates areas recursively, thereby considering left and right segments separated by previously determined minimal height - or "pivot" - as the rectangular height at that segment.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), with potential for worse case involving complete traversal checks.
Space Complexity: O(n) for recursive calls.

Try this approach in the editor ā†’

Approach 3: Monotonic Stack

We can enumerate the height h of each bar as the height of the rectangle. Using a monotonic stack, we find the index left_i, right_i of the first bar with a height less than h to the left and right. The area of the rectangle at this time is h times (right_i-left_i-1). We can find the maximum value.

The time complexity is O(n), and the space complexity is O(n). Here, n represents the length of heights.

Common model of monotonic stack: Find the nearest number to the left/right of each number that is larger/smaller than it. Template:

stk = []
for i in range(n):
    while stk and check(stk[-1], i):
        stk.pop()
    stk.append(i)

Code

PythonJavaC++GoRustC#

Python

Java

C++

Go

Rust

C#

Try this approach in the editor ā†’

Approach 4: Default Approach

Code

Python

Python

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Monotonic Stack Method

Time Complexity: O(n), where n is the number of bars (height array length), since each bar is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack.

Divide and Conquer

Time Complexity: O(n^2), with potential for worse case involving complete traversal checks.
Space Complexity: O(n) for recursive calls.

Monotonic Stackā€”
Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Divide and ConquerAverage O(n log n), Worst O(nĀ²)O(log n)Useful for conceptual understanding or when practicing recursive partitioning techniques
Monotonic StackO(n)O(n)Best general solution and the approach typically expected in coding interviews

Video Solution

LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python ā€¢ NeetCode ā€¢ 414,734 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Largest Rectangle in Histogram easy or hard?
Largest Rectangle in Histogram is classified as a Hard problem on LeetCode because the optimal solution requires recognizing a monotonic stack pattern. Many developers first attempt O(n^2) brute force approaches before discovering the linear stack-based optimization.
How to solve Largest Rectangle in Histogram in O(n)?
Use a monotonic increasing stack that stores indices of bars. Iterate through the histogram and maintain increasing heights. When a smaller height appears, pop bars from the stack and compute areas using the popped height as the limiting factor and the current index as the right boundary. Each index is processed once, giving linear time complexity.
Largest Rectangle in Histogram Python or Java solution
Both Python and Java implementations follow the same monotonic stack idea. Iterate through the histogram, push indices of increasing heights, and when a smaller bar appears, pop from the stack and compute areas using width derived from the current index and the new stack top. This guarantees O(n) runtime.
What is the best approach for Largest Rectangle in Histogram?
The monotonic stack approach is the most efficient and commonly used solution. It processes each bar once while maintaining indices of increasing heights in a stack. Whenever a smaller bar appears, rectangles are calculated using popped bars as the minimum height. This achieves O(n) time complexity with O(n) space.
What data structure is used in Largest Rectangle in Histogram?
The optimal solution relies on a stack, specifically a monotonic stack that maintains bars in increasing height order. The stack helps quickly determine the nearest smaller element on both sides of each bar, which defines the maximum width where that bar can form a rectangle.
What is the time complexity of Largest Rectangle in Histogram?
The optimal solution using a monotonic stack runs in O(n) time because each bar is pushed and popped from the stack at most once. A divide and conquer solution typically runs in O(n log n) on average but can degrade to O(n^2) in the worst case when the minimum element repeatedly splits the array unevenly.
Is Largest Rectangle in Histogram asked at Google, Amazon, or Meta?
Largest Rectangle in Histogram is a well-known hard interview problem frequently asked at large tech companies including Amazon, Google, Meta, and Microsoft. It tests understanding of stacks, boundary expansion problems, and algorithmic optimization from quadratic to linear time.

Ready to solve this problem?

Practice Largest Rectangle in Histogram with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximal Rectangle

Next

Maximum Score of a Good Subarray