What is the best approach to solve Largest Rectangle in Histogram?

The optimal approach for Largest Rectangle in Histogram is the "Optimal — Monotonic Stack" technique. It runs in O(n) time and uses O(n) space. Use a stack of indices in increasing height order. When a shorter bar is found, pop taller bars — each popped bar's width extends back to the current stack top. This finds each bar's 'largest rectangl

What is the time complexity of Largest Rectangle in Histogram?

The optimal solution for Largest Rectangle in Histogram has a time complexity of O(n) and a space complexity of O(n), achieved using the Monotonic Stack pattern.

Is Largest Rectangle in Histogram a Hard LeetCode problem?

Yes, LeetCode #84 (Largest Rectangle in Histogram) is rated Hard. It uses the Monotonic Stack pattern and is commonly asked in interviews at Amazon, Google, Microsoft.

How to solve Largest Rectangle in Histogram in Python, Java, C++, and JavaScript?

LumiChats provides complete solutions for Largest Rectangle in Histogram in Python, Java, C++, and JavaScript, along with step-by-step visual animations and time/space complexity analysis. All solutions are free to view.

#84HardMonotonic Stack

Largest Rectangle in Histogram

Monotonic stack finds each bar's left/right boundary in O(n).

AmazonGoogleMicrosoftDeutsche Bank

Problem Statement

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

Examples

Example 1

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

Output:10

Explanation: The rectangle spans bars 2-3 (heights 5 and 6), area = 5×2 = 10.

Example 2

Input:heights = [2,4]

Output:4

Constraints

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

Solutions

Brute Force — Try all bar pairs

TimeO(n²)SpaceO(1)

For each pair (i, j), the rectangle height is min(heights[i..j]) and width is j-i+1. O(n²) or O(n³).

Visual Animation

def largestRectangleArea(heights: list[int]) -> int:
    best = 0
    for i in range(len(heights)):
        min_h = heights[i]
        for j in range(i, len(heights)):
            min_h = min(min_h, heights[j])
            best = max(best, min_h * (j - i + 1))
    return best

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine Learning Browse all 190+ concepts →

Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Monotonic Stack to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems

39+

AI Models

₹69

Per day used

Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free

Back to all problems