Log inSign up
hardLeetCodeNot Started

Largest Rectangle in Histogram

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

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 · Standard Histogram:

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle is formed by bars [5, 6] with height 5 and width 2 -> area = 5 * 2 = 10.

Example 2 · Uniform Height:

Input: heights = [2, 4]
Output: 4
Explanation: The bar of height 4 gives area 4 * 1 = 4. Alternatively, height 2 gives area 2 * 2 = 4.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the core principle: fixing each bar as the minimum height and expanding boundaries to the left and right.
  • Master the single-pass monotonic stack technique with sentinel values.
  • Apply this building block to solve 2D binary matrix area problems (Maximal Rectangle).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Maintain a monotonic increasing stack of indices.
  • For each index i from 0 to N (using height 0 at index N as sentinel):
  • While stack is not empty and currHeight < heights[st.top()], pop mid = st.pop().
  • The height is heights[mid].
  • The left boundary is st.empty() ? -1 : st.top().
  • The right boundary is i.
  • area = height * (right - left - 1). Update maxArea = max(maxArea, area).

Connected Patterns:

Maximal RectangleTrapping Rain WaterNext Smaller Element

1. All Pairs Boundary Scan

Intuition

For each bar i, fix heights[i] as the rectangle height. Expand left as long as heights[j] >= heights[i] and expand right as long as heights[k] >= heights[i]. Calculate area = height * (right - left + 1).

Algorithm

  1. Step 1: Initialize maxArea = 0.
  2. Step 2: Loop i from 0 to N - 1 with h = heights[i].
  3. Step 3: Find left: decrement from i while left >= 0 && heights[left] >= h.
  4. Step 4: Find right: increment from i while right < N && heights[right] >= h.
  5. Step 5: area = h * (right - left - 1). Update maxArea = max(maxArea, area).
  6. Step 6: Return maxArea.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int largestRectangleArea(std::vector<int>& heights) {
8 int n = heights.size();
9 int maxArea = 0;
10 for (int i = 0; i < n; i++) {
11 int h = heights[i];
12 int left = i;
13 while (left >= 0 && heights[left] >= h) {
14 left--;
15 }
16 int right = i;
17 while (right < n && heights[right] >= h) {
18 right++;
19 }
20 int width = right - left - 1;
21 maxArea = std::max(maxArea, h * width);
22 }
23 return maxArea;
24 }
25};
26
27int main() {
28 Solution solver;
29 std::vector<int> heights = {2, 1, 5, 6, 2, 3};
30 std::cout << "Max Area: " << solver.largestRectangleArea(heights) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N^2) — For every bar i, scan left to find the left boundary and scan right to find the right boundary.
  • Space complexity: O(1) — O(1) extra space.

Why Brute Force Doesn't Scale:

At N = 100,000, O(N2) requires 1010 operations.

Single-pass Monotonic Stack solves N = 100,000 in <15ms.

2. Two-Pass Precomputed Boundaries (PSE & NSE)

Intuition

Precompute leftSmaller[i] and rightSmaller[i] arrays using two separate monotonic stack passes, then find the max area in a third pass.

Algorithm

  1. Step 1: Compute leftSmaller array where leftSmaller[i] is the index of the first smaller element to the left (or -1).
  2. Step 2: Compute rightSmaller array where rightSmaller[i] is the index of the first smaller element to the right (or N).
  3. Step 3: Loop i from 0 to N - 1: area = heights[i] * (rightSmaller[i] - leftSmaller[i] - 1).
  4. Step 4: Update maxArea = max(maxArea, area) and return maxArea.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5
6class Solution {
7public:
8 int largestRectangleArea(std::vector<int>& heights) {
9 int n = heights.size();
10 std::vector<int> leftSmaller(n), rightSmaller(n);
11 std::stack<int> st;
12
13 // Compute Previous Smaller Elements
14 for (int i = 0; i < n; i++) {
15 while (!st.empty() && heights[st.top()] >= heights[i]) {
16 st.pop();
17 }
18 leftSmaller[i] = st.empty() ? -1 : st.top();
19 st.push(i);
20 }
21
22 while (!st.empty()) st.pop();
23
24 // Compute Next Smaller Elements
25 for (int i = n - 1; i >= 0; i--) {
26 while (!st.empty() && heights[st.top()] >= heights[i]) {
27 st.pop();
28 }
29 rightSmaller[i] = st.empty() ? n : st.top();
30 st.push(i);
31 }
32
33 int maxArea = 0;
34 for (int i = 0; i < n; i++) {
35 int width = rightSmaller[i] - leftSmaller[i] - 1;
36 maxArea = std::max(maxArea, heights[i] * width);
37 }
38 return maxArea;
39 }
40};
41
42int main() {
43 Solution solver;
44 std::vector<int> heights = {2, 1, 5, 6, 2, 3};
45 std::cout << "Max Area: " << solver.largestRectangleArea(heights) << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N) — Precomputing previous smaller indices in one pass and next smaller indices in a second pass takes 2 * O(N) = O(N) time.
  • Space complexity: O(N) — O(N) arrays for prevSmaller and nextSmaller indices.

3. Optimal Single-Pass Monotonic Stack

Intuition

Whenever a bar of smaller height is encountered, the bar at the top of the stack has found its right boundary (current index i) and its left boundary is the index below it on the stack. We compute its area immediately upon popping.

Algorithm

  1. Step 1: Initialize an empty stack st and maxArea = 0.
  2. Step 2: Loop i from 0 to N (at i = N, treat currHeight = 0 to flush the stack).
  3. Step 3: While stack is non-empty and currHeight < heights[st.top()]:
  4. - h = heights[st.pop()]
  5. - left = st.empty() ? -1 : st.top()
  6. - width = i - left - 1
  7. - maxArea = max(maxArea, h * width)
  8. Step 4: Push i onto st.
  9. Step 5: Return maxArea.

Largest Rectangle in Histogram Single-Pass Monotonic Stack Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
Current operationSTEP 1 OF 7
Stack: [0]
Visual state
Values and pointers at this exact step
stack
TOP
idx 0 (h:2)
Push adds to the top · Pop removes from the top
Why this step matters

Stack: [0]

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5
6class Solution {
7public:
8 int largestRectangleArea(std::vector<int>& heights) {
9 int n = heights.size();
10 std::stack<int> st;
11 int maxArea = 0;
12 for (int i = 0; i <= n; i++) {
13 int currHeight = (i == n) ? 0 : heights[i];
14 while (!st.empty() && currHeight < heights[st.top()]) {
15 int h = heights[st.top()];
16 st.pop();
17 int left = st.empty() ? -1 : st.top();
18 int width = i - left - 1;
19 maxArea = std::max(maxArea, h * width);
20 }
21 st.push(i);
22 }
23 return maxArea;
24 }
25};
26
27int main() {
28 Solution solver;
29 std::vector<int> heights = {2, 1, 5, 6, 2, 3};
30 std::cout << "Max Area: " << solver.largestRectangleArea(heights) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Every index is pushed onto the stack once and popped once in a single unified pass.
  • Space complexity: O(N) — O(N) space for the stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Pairs Boundary ScanO(N^2)O(1)Scan left and right from each bar.Repeated linear scanning across flat/increasing subranges.
2.Two-Pass Precomputed BoundariesO(N)O(N)Precompute PSE and NSE in 2 separate passes using monotonic stacks.Memory allocation for 2 full auxiliary arrays.
3.Optimal Single-Pass Monotonic StackOptimalO(N)O(N)Resolve left and right boundaries simultaneously during popping with a sentinel height 0.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using < instead of <= or not handling duplicate heights in left/right arrays.

Pitfall 2:

Off-by-one errors when calculating width (right - left - 1).

Pitfall 3:

Forgetting to process remaining elements after the main loop.

Crucial Edge Cases to Validate:

  • All bars of equal height `[2, 2, 2, 2]` — The rectangle spans all bars: 2 * 4 = 8.
  • Strictly increasing heights `[1, 2, 3, 4, 5]` — Handled cleanly by sentinel flush at index N.
  • Strictly decreasing heights `[5, 4, 3, 2, 1]` — Every step triggers immediate pops.
  • Single bar `[7]` — Area is 7 * 1 = 7.
  • Bars with height 0 `[0, 9, 0]` — Area is 9.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Frame the problem around the core question: 'For each bar, what is the maximum width it can span as the limiting (minimum) height?'.
  2. Explain the boundary invariant: width = nextSmaller - prevSmaller - 1.
  3. Show how the sentinel height = 0 at index N elegantly flushes the stack without needing boilerplate cleanup loops.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When a bar is popped from the monotonic increasing stack, what are its left and right boundaries?

2.Why do we iterate up to index N with height 0 in the optimal single-pass approach?

Back to DSA Sheet