Largest Rectangle in Histogram

hard monotonic stack array

Problem

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.

Inputheights = [2, 1, 5, 6, 2, 3]

Output10

A monotonic-increasing stack of indices lets us pop on each shorter bar to find that bar's max-area rectangle.

heights (comma-separated, ≥ 0)

def largest_rectangle_area(heights):
    stack = []
    best = 0
    for i in range(len(heights) + 1):
        h = 0 if i == len(heights) else heights[i]
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        stack.append(i)
    return best

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

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

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int best = 0, n = heights.size();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!st.empty() && heights[st.top()] > h) {
            int top = st.top(); st.pop();
            int left = st.empty() ? -1 : st.top();
            best = max(best, heights[top] * (i - left - 1));
        }
        st.push(i);
    }
    return best;
}

Explanation

For each bar, the biggest rectangle using that bar as the shortest one stretches left and right until it hits a shorter bar. The challenge is finding those left and right boundaries fast. A monotonic increasing stack of indices does exactly that in one pass.

We keep a stack where bar heights increase from bottom to top. When a new bar h is shorter than the bar on top, that top bar can no longer extend right, so we pop it and finalize its rectangle right now.

When we pop index top, the height is heights[top]. The right edge is the current i (the first shorter bar), and the left edge is the new stack top plus one. So the width is i - left - 1 and the area is heights[top] * width. We track the best area seen.

A neat trick: we loop one step past the end and treat that as a virtual bar of height 0, which forces every remaining bar to be popped and measured.

Example: heights = [2, 1, 5, 6, 2, 3]. When the 2 after 6 arrives, we pop 6 (area 6) then 5 (area 10, spanning indices 2–3). That 10 is the largest rectangle.

Time: O(n) Space: O(n)