The O(n) Club: Largest Rectangle in Histogram: Unleash the Monotonic Stack Mayhem

The O(n) Club: Largest Rectangle in Histogram – Unleash the Monotonic Stack Mayhem

⚡ TL;DR

Want to find the biggest rectangle under a histogram? If you use brute force, your code will age like milk (O(n²) sadness). Use a monotonic stack for O(n) glory. Java style:

// Slow & steady loses this race:
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
    int min = heights[i];
    for (int j = i; j < heights.length; j++) {
        min = Math.min(min, heights[j]);
        maxArea = Math.max(maxArea, min * (j - i + 1));
    }
}
// Time complexity: O(n^2). Interviewer facepalms.

🧠 How Devs Usually Mess This Up

Tempted to expand each bar left and right until the height dips? That’s the classic rookie move—welcome to timeouts and hair loss. The real crime? Failing to invite the Monotonic Stack to the party. Trying to eyeball rectangle width on the fly is a recipe for off-by-one heartbreak. Bottom line: You think it’s about rectangles, but it’s all about remembering where the walls are.

🔍 What’s Actually Going On

Imagine your histogram bars as cocky robots at a dance-off. Each thinks they’re the star until a shorter robot waltzes in and kicks them off the floor (aka the stack). The stack? It’s the VIP list for bars who can potentially flex the widest rectangle—until they’re rudely interrupted. When a shorty shows up, we kick tall bars out and tally up the best rectangle they ever could’ve had, right then and there. No more: ‘let’s expand both directions and hope.’

🛠️ PseudoCode

• Append a zero bar to the end so everyone gets their moment to shine before closing time.
• Create an empty stack to hold indices, not heights—because Java, and because it lets you track positions fast.
• For each bar (by index i):
  • If stack is empty or current bar is taller than stack’s top: Push i.
  • If a bar is shorter than the one on top of the stack:
    • Pop from stack. Now, the bar at that popped index can’t go any further to the right.
    • Area is: height[popped] * width. Width is (i – stack[top] – 1) or i if stack is empty.
    • Update max area, because even robots have aspirations.
  • Keep popping until stack is safe (either empty or current bar is taller).

💻 The Code

import java.util.Stack;
 public class HistogramRectangle {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] newHeights = new int[n + 1];
        System.arraycopy(heights, 0, newHeights, 0, n);
        newHeights[n] = 0; // Zero ensures we pop all remaining bars
         Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
         for (int i = 0; i < newHeights.length; i++) {
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                int height = newHeights[stack.pop()];
                int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Forgotten zero at the end? Enjoy stacking up stale bars forever.
• Width calculation disasters: Remember, if the stack’s empty, width is the current index. Otherwise, it’s the gap between indices, minus one (classic off-by-one drama).
• All bars same height? Stack handles it, but test edge cases to dodge nasty surprises.
• Brutal time/space: O(n). Every bar is pushed and popped just once (no, this isn’t a trick question).

🧠 Interviewer Brain-Tattoo

If you’re hand-scanning left and right for boundaries in a histogram, you’re working too hard—let the stack sweat while you sip your coffee and prep for your happy dance.