Pattern visualizer
Largest Rectangle in Histogram
Every rectangle is capped by its own shortest bar, so ask of each bar: how far left and right can it stretch before something shorter blocks it? Scanning left to right, a bar's right edge is decided the moment a shorter bar appears — and until then the bar is still open. A stack holding indices in increasing height order remembers exactly the open bars, and because it is sorted, whatever sits below a popped bar is the first shorter bar to its LEFT. So one pop hands you both edges at once, each bar is pushed and popped once, and the whole thing runs in a single O(n) pass. Animated on: heights = [2, 1, 5, 6, 2, 3] — find the largest rectangle that fits entirely inside the histogram..
Monotonic increasing stack of indices
Bars 2, 1, 5, 6, 2, 3, plus an appended 0-height bar at index 6 so every real bar is forced off the stack and measured. The stack keeps indices whose heights only ever increase.
1FUNCTION largestRectangle(H):2 APPEND 0 TO H3 stack <- [-1]4 best <- 05 FOR i <- 0 TO LENGTH(H) - 1:6 WHILE TOP(stack) != -1 AND H[TOP(stack)] > H[i]:7 top <- POP(stack)8 width <- i - TOP(stack) - 19 best <- MAX(best, H[top] * width)10 PUSH i ONTO stack11 RETURN best
← / → step · space play · Home restart