Largest Rectangle in Histogram

This one looks like a drawing puzzle but it is really a stack puzzle. Many people get stuck because they try every rectangle by hand. The interviewer wants to see if you can spot when a stack turns a slow scan into a fast one. So this question is a classic test of the monotonic stack idea.

🎯 The Problem

You get a list of bar heights and must find the biggest rectangle that fits fully inside the bars.

• Each bar has a width of 1. Think of it like a bar chart.
• A rectangle is a flat block resting inside the bars.
• Its height is limited by the shortest bar it covers.
• Its width is how many bars it stretches across.
• The answer is the largest area, where area is height times width.

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

Explanation: bars at index 2 and 3 have heights 5 and 6.
The shortest of them is 5, and the width is 2 bars.
So area = 5 * 2 = 10, which is the largest possible.

Here is the bar chart for that input. Notice how bars 5 and 6 sit next to each other and form the tall block.

🐢 Approach 1: Try Every Range (Brute Force)

Pick a start bar, slide right, and track the shortest bar as the height.

The idea:

• Loop a start bar over every position.
• Loop an end bar from the start to the right.
• Track the shortest bar seen so far in that range. That is the height.
• The bar count is the width. Area is height times width. Keep the biggest.

Why it is weak:

• For every start you scan all the way to the end.
• That is two nested loops over n bars.
• Time is O(n²). It rescans the same bars again and again.

Here is the try-every-range code:

def largest_rectangle_area(heights):
    best = 0
    for left in range(len(heights)):
        smallest = heights[left]
        for right in range(left, len(heights)):
            smallest = min(smallest, heights[right])
            best = max(best, smallest * (right - left + 1))
    return best

⚡ Approach 2: Monotonic Increasing Stack (Best)

The idea in one line: for each bar, find the widest stretch where that bar is the shortest one, using a stack that only grows in height.

The idea:

• For each bar ask: how far left and right can it stretch before hitting a shorter bar?
• A monotonic increasing stack is a stack whose heights only go up from bottom to top.
• Store indexes in it, not heights, so widths can be measured later.

How it works:

• Walk the bars left to right.
• While the bar on top of the stack is taller than the current bar, pop it. That taller bar can stretch no further right.
• On a pop, the current index is the right edge. The new stack top is the left edge.
• Width is the gap between those edges. Height is the popped bar. Multiply for the area and keep the best.
• Add a fake bar of height 0 at the very end. It is shorter than everything, so it forces every leftover bar to pop and get measured.

Why it is fast:

• Each bar is pushed once and popped once.
• So the whole scan is O(n).
• A shorter bar settles the rectangles for all taller bars behind it at once.

Here is the stack changing as we scan [2, 1, 5, 6, 2, 3]. Watch how popping a taller bar gives us a finished rectangle.

Steps to Solve

1. Create an empty stack that will hold bar indexes.
2. Walk through the bars from left to right. Treat the position after the last bar as a fake bar of height 0.
3. While the stack is not empty and the bar at the top is taller than the current bar, pop the top.
4. For the popped bar, its height is its own height. Its width reaches from the new stack top up to the current index.
5. Compute area as height times width and update the best area.
6. After popping, push the current index onto the stack.
7. When the scan ends, the best area is the answer.

#include <stdio.h>

int largestRectangleArea(int heights[], int n) {
    int stack[100000];   // holds indexes
    int top = -1;        // stack is empty
    int best = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : heights[i];  // fake 0 bar at the end
        while (top >= 0 && heights[stack[top]] > cur) {
            int height = heights[stack[top]]; // popped bar's height
            top--;
            int leftEdge = (top < 0) ? -1 : stack[top];
            int width = i - leftEdge - 1;     // bars between edges
            int area = height * width;
            if (area > best) best = area;
        }
        stack[++top] = i;  // push current index
    }
    return best;
}

int main(void) {
    int heights[] = {2, 1, 5, 6, 2, 3};
    int n = 6;
    printf("%d\n", largestRectangleArea(heights, n));
    return 0;
}

10

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;        // holds indexes
    int n = heights.size();
    int best = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : heights[i];  // fake 0 bar at the end
        while (!st.empty() && heights[st.top()] > cur) {
            int height = heights[st.top()];   // popped bar's height
            st.pop();
            int leftEdge = st.empty() ? -1 : st.top();
            int width = i - leftEdge - 1;     // bars between edges
            best = max(best, height * width);
        }
        st.push(i);  // push current index
    }
    return best;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << largestRectangleArea(heights) << endl;
    return 0;
}

10

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangle {
    public static int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();  // holds indexes
        int n = heights.length;
        int best = 0;
        for (int i = 0; i <= n; i++) {
            int cur = (i == n) ? 0 : heights[i];   // fake 0 bar at the end
            while (!stack.isEmpty() && heights[stack.peek()] > cur) {
                int height = heights[stack.pop()]; // popped bar's height
                int leftEdge = stack.isEmpty() ? -1 : stack.peek();
                int width = i - leftEdge - 1;      // bars between edges
                best = Math.max(best, height * width);
            }
            stack.push(i);  // push current index
        }
        return best;
    }

    public static void main(String[] args) {
        int[] heights = { 2, 1, 5, 6, 2, 3 };
        System.out.println(largestRectangleArea(heights));
    }
}

10

def largest_rectangle_area(heights):
    stack = []            # holds indexes
    n = len(heights)
    best = 0
    for i in range(n + 1):
        cur = 0 if i == n else heights[i]   # fake 0 bar at the end
        while stack and heights[stack[-1]] > cur:
            height = heights[stack.pop()]   # popped bar's height
            left_edge = stack[-1] if stack else -1
            width = i - left_edge - 1       # bars between edges
            best = max(best, height * width)
        stack.append(i)                     # push current index
    return best


heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))

10

function largestRectangleArea(heights) {
  const stack = []; // holds indexes
  const n = heights.length;
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const cur = i === n ? 0 : heights[i]; // fake 0 bar at the end
    while (stack.length && heights[stack[stack.length - 1]] > cur) {
      const height = heights[stack.pop()]; // popped bar's height
      const leftEdge = stack.length ? stack[stack.length - 1] : -1;
      const width = i - leftEdge - 1; // bars between edges
      best = Math.max(best, height * width);
    }
    stack.push(i); // push current index
  }
  return best;
}

const heights = [2, 1, 5, 6, 2, 3];
console.log(largestRectangleArea(heights));

10

Let us walk through the Python version line by line so the stack logic is clear.

stack = [] starts an empty list that will hold indexes. We store indexes, not heights, because we need the index to measure how wide a rectangle is.

for i in range(n + 1): loops one step past the end. That extra step is where the fake bar lives.

cur = 0 if i == n else heights[i] sets the current height. On the very last step i equals n, so we use 0. That 0 is shorter than every real bar. It forces the stack to empty out and measure every bar left inside.

while stack and heights[stack[-1]] > cur: checks the bar on top of the stack. If that top bar is taller than the current bar, the top bar cannot stretch any further right. So we must measure it now.

height = heights[stack.pop()] pops the top index and reads its height. This popped bar is the height of the rectangle we are about to measure.

left_edge = stack[-1] if stack else -1 looks at the new top of the stack. That is the nearest shorter bar on the left. If the stack is empty, nothing blocks us on the left, so the left edge is -1.

width = i - left_edge - 1 counts the bars strictly between the left edge and the current index i. The current index is the right edge. So the rectangle covers everything between, and that is its width.

best = max(best, height * width) keeps the largest area we have seen.

stack.append(i) pushes the current index. After all taller bars are popped, the stack stays increasing, which is exactly the monotonic property we rely on.

⏱️ Time and Space Complexity

The brute force scans every range, so it costs O(n²) time but almost no extra memory. The monotonic stack pushes and pops each index exactly once. So the whole scan is O(n) time. The stack can hold up to n indexes, so it needs O(n) extra memory. You trade a little memory for a big speed gain.

🧩 Key Takeaways

• ✅ Each bar is the limiting height for the widest block where it is the shortest bar.
• ✅ A monotonic increasing stack stores indexes whose right edge is not known yet.
• ✅ When a shorter bar appears, pop the taller bars and measure their rectangles right then.
• ✅ Width is the gap between the new stack top and the current index, so store indexes, not heights.
• ✅ Adding a fake 0 bar at the end clears the stack and measures every leftover bar.

🚀 What’s Next?

• Asteroid Collision
• Basic Calculator II