Stack/Largest Rectangle in HistogramHard

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Largest Rectangle in Histogram

Stack·Hard

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.

The optimal solution uses a monotonic increasing stack of indices: for each bar, while the top of the stack is taller than the current bar, pop it and treat it as the shortest bar in a rectangle that extends from the new top of the stack (exclusive) to the current index (exclusive).

Examples

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

Output: 10

The largest rectangle has area 10, formed by the bars of heights 5 and 6 over width 2.

Input: heights = [2,4]

Output: 4

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Stack
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.