34. Largest Rectangle in Histogram

HardStacks, Queues & Monotonic StacksAlso on LeetCode ↗

heights describes a histogram whose bars have width 1. Return the area of the largest rectangle that fits inside it.

Example 1

Input: heights = [2,4,2,1]

Output: 6

Explanation: Height 2 across the first three bars: 2 × 3 = 6.

Example 2

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

Output: 12

Hint 1

For each bar, the widest rectangle of that height stretches until a shorter bar on each side.

Hint 2

A stack of increasing heights tells you both boundaries when a bar is popped.

Monotonic Stack

Reference solution for Monotonic stack (time O(n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []                     # indices with increasing heights
        best = 0
        for i, h in enumerate(heights + [0]):      # sentinel 0 flushes the stack
            while stack and heights[stack[-1]] >= h:
                top = heights[stack.pop()]
                left = stack[-1] + 1 if stack else 0  # bar `top` extends from left to i-1
                best = max(best, top * (i - left))
            stack.append(i)
        return best

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();   // indices with increasing heights
        int best = 0, n = heights.length;
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];       // sentinel flushes the stack
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int top = heights[stack.pop()];
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                best = Math.max(best, top * (i - left));
            }
            stack.push(i);
        }
        return best;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> st;                              // indices with increasing heights
        int best = 0, n = heights.size();
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];       // sentinel flushes the stack
            while (!st.empty() && heights[st.back()] >= h) {
                int top = heights[st.back()]; st.pop_back();
                int left = st.empty() ? 0 : st.back() + 1;
                best = max(best, top * (i - left));
            }
            st.push_back(i);
        }
        return best;
    }
};

function largestRectangleArea(heights) {
  const stack = []; // indices with increasing heights
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i]; // sentinel flushes the stack
    while (stack.length && heights[stack[stack.length - 1]] >= h) {
      const top = heights[stack.pop()];
      const left = stack.length ? stack[stack.length - 1] + 1 : 0;
      best = Math.max(best, top * (i - left));
    }
    stack.push(i);
  }
  return best;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

34. Largest Rectangle in Histogram

Example 1

Example 2

Approach 1: Expand around each bar

Approach 2: Monotonic stack ✅