Leetcode 84: Largest Rectangle in Histogram

 

1. Problem Statement (Simple Explanation)

You’re given an array heights where:

• heights[i] is the height of the i-th bar.

• Each bar has width 1.

You must return the area of the largest rectangle that can be formed in the histogram:

• The rectangle must be contiguous (i.e., cover a continuous range of bars).

• The rectangle’s height is limited by the shortest bar in that interval.

2. Examples

Example 1:

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

Largest rectangle:

• Using bars with heights 5 and 6 (indices 2 and 3).

• Minimum height in that range = 5, width = 2 → area = 5 * 2 = 10.

Output: 10

Example 2:

Input: heights = [2,4]

Best options:

• Bar 0 alone: area = 2

• Bar 1 alone: area = 4

• Both bars: min height = 2, width = 2 → area = 4

Max area = 4.

Output: 4

3. Approach – Monotonic Stack (O(n))

A brute-force approach (checking all possible ranges) is O(n²) and too slow for n up to 10^5.

We use a monotonic increasing stack to compute, for each bar, the largest rectangle where that bar is the shortest.

Key Insight:

For each index i, consider heights[i] as the limiting height (shortest bar) in some maximal range [L+1 .. R-1]:

• To the left, find the index of the previous smaller bar.

• To the right, find the index of the next smaller bar.

Then bar i can extend from (L+1) to (R-1).

Area with bar i as the smallest = heights[i] * (R - L - 1).

We can compute these bounds using a single stack pass.

Classic Stack Technique:

Use a stack to store indices of bars in increasing height order:

1. Append a sentinel 0 height at the end of the array (or process to n and then flush the stack) to force popping all bars.

2. Iterate i from 0 to n:

• While stack is not empty and heights[i] < heights[stack.top()]:

• Pop top as mid → height = heights[mid].

• Right boundary = current index i.

• Left boundary:

• If stack is empty after pop → left = -1.

• Else left = stack.top().

• Width = right - left - 1.

• Area = height * width, update maxArea.

• Push i onto stack.

By maintaining indices of bars with increasing heights, when we see a shorter bar, we know the popped bar's right boundary, and the new stack top gives us the left boundary.

Pseudo-code:

Complexity:

Let n = len(heights):

• Each index is pushed and popped at most once.

• Time: O(n)

• Space: O(n) for the stack.

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code