Largest Rectangle in Histogram

Hard

monotonic-stack

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.

Key Insight: For each bar, we need to find how far left and right it can extend (until we hit a shorter bar). A monotonic increasing stack naturally gives us this information: when we pop a bar, the current bar is the right boundary, and the new stack top is the left boundary.

The width of the rectangle with height heights[popped] is:

If stack is empty: i (extends from index 0)
Otherwise: i - stack.top() - 1

Trick: Add a sentinel bar of height 0 at the end to force all remaining bars to be processed.

Example 1

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

Output: 10

Explanation: The largest rectangle has area = 5 * 2 = 10 (formed by bars at indices 2 and 3).

Example 2

Input: heights = [2,4]

Output: 4

Explanation: Maximum is either 2*2=4 (using both bars) or 4*1=4 (just the tall bar).

Constraints

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

Show Hints (4)

Hint 1: For each bar, if we knew how far left and right it could extend, we could compute its rectangle area.

Hint 2: When we pop a bar from the stack, the current index is its right boundary.

Hint 3: The new stack top after popping gives the left boundary.

Hint 4: Add a 0-height bar at the end to ensure all bars get processed (sentinel technique).

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?