A warehouse rack is a row of bays, each already stacked to a known height of unit-width bins. Slotting needs the largest rectangular block of contiguous bays it can reserve for a new SKU — the block’s height is limited by the shortest bay in that span. The intern version, for each bay i, walked left and right while neighbors were at least as tall as heights[i], then multiplied. A dozen bays returned in milliseconds. A kilometer of pick-face was still expanding when the slotting job timed out.

Largest Rectangle in Histogram asks for the max area of contiguous unit-width bars. Nested expand uses that and still pays O(n²). The nearest strictly shorter bar to the left and to the right bound the width; sorting would destroy the bay order that width needs.

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about a monotonic increasing stack of indexes so a shorter bar closes every taller bar it dominates. Same family as Daily Temperatures (next greater / waiting indexes) and Car Fleet (leaders / times). Do not re-solve the waits or the fleets on this prompt.

The problem

Given an int[] heights of non-negative bar heights, each bar width 1, return the largest rectangle area that can be formed using contiguous bars. The rectangle’s height is limited by the shortest bar in that span.

heights = [2, 1, 5, 6, 2, 3]  →  10
heights = [2, 4]              →  4
heights = [2, 2, 2]           →  6

In the first row, bars 5 and 6 form height 5 times width 2 = 10. The four bars from index 2 through 5 form height 2 times width 4 = 8. The whole row is height 1 times width 6 = 6. Ten wins. The third row is the plateau: three equal bars, one rectangle of area 6.

Note: The return is an area, not a pair of indexes. If they wanted the span, the same walk works and you keep the left/i pair that produced the max. Do not mix the two prompts.

Nested expand is the honest brute force

For each i, walk left while the neighbor is >= heights[i], walk right the same way, then area = heights[i] * (right - left + 1). Correct. Quadratic.

int largestRectangleAreaNested(int[] heights) {
    int n = heights.length;
    int max = 0;
    for (int i = 0; i < n; i++) {
        int left = i;
        while (left > 0 && heights[left - 1] >= heights[i]) {
            left--;
        }
        int right = i;
        while (right + 1 < n && heights[right + 1] >= heights[i]) {
            right++;
        }
        max = Math.max(max, heights[i] * (right - left + 1));
    }
    return max;
}

At n = 30 this is a rounding error. At a long pick-face you paid a nested expand for a question a stack answers because one shorter bar closes every taller bar still open to its left: is this bar strictly shorter than the one still open on top?

Increasing stack of bar indexes

The stack holds indexes of bars whose rectangle can still grow right. Heights at those indexes are non-decreasing from bottom to top — a monotonic increasing stack. Walk i from 0 to n inclusive. Treat i == n as a sentinel of height 0 so leftover bars flush in the same loop.

  • While the stack is not empty and h is strictly shorter than heights[bars.peek()], pop j. Bar j can no longer grow right: i is the first strictly shorter bar to its right (or n). The left boundary is the new peek, or -1 if the stack is empty. Width is i - left - 1. Area is heights[j] * width.
  • If i < n, push i. It is now the newest bar still open to the right.

Do not push the sentinel index. There is no heights[n].

Walk the first sample. Stack contents are indexes; the heights are only for the comparison.

heights = [2, 1, 5, 6, 2, 3]
n = 6, sentinel h=0 at i=6

i=0  h=2   []              push 0                      [0]
i=1  h=1   1<2  pop 0      left=-1  width=1  area=2
                           push 1                      [1]
i=2  h=5   5<1? no         push 2                      [1, 2]
i=3  h=6   6<5? no         push 3                      [1, 2, 3]
i=4  h=2   2<6  pop 3      left=2   width=1  area=6
           2<5  pop 2      left=1   width=2  area=10
           2<1? no         push 4                      [1, 4]
i=5  h=3   3<2? no         push 5                      [1, 4, 5]
i=6  h=0   0<3  pop 5      left=4   width=1  area=3
           0<2  pop 4      left=1   width=4  area=8
           0<1  pop 1      left=-1  width=6  area=6

max = 10

Index 4 (2) closed bars 6 and 5 in one step — that is the 5 × 2 = 10 rectangle. The sentinel closed the height-2 span of width 4 (area 8) and the height-1 span of width 6. You never rescan a popped bar.

The Java is that walk. The stack stores indexes, not heights.

int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int max = 0;
    Deque<Integer> bars = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!bars.isEmpty() && h < heights[bars.peek()]) {
            int j = bars.pop();
            int left = bars.isEmpty() ? -1 : bars.peek();
            int width = i - left - 1;
            max = Math.max(max, heights[j] * width);
        }
        if (i < n) {
            bars.push(i);
        }
    }
    return max;
}

Time is O(n) — each index is pushed once and popped at most once. Space is O(n) for the stack (a non-decreasing histogram never pops until the sentinel). Do not quote the nested O(n²) as the intended bill.

Store indexes, not heights. A stack of heights can tell you that a shorter bar arrived; it cannot tell you the width. Equal heights do not pop under h < heights[peek]. They stay; the leftmost equal bar of a plateau gets the full width when it pops later. Popping on <= is also correct if you use it everywhere — pick one rule and keep it.

Note: left = peek after the pop, not before. Width is i - left - 1, not i - j. If the stack is empty after the pop, the rectangle runs to the start of the array (left = -1).

What interviewers usually poke next

  • Same monotonic family. Daily Temperatures holds waiting indexes for a strictly greater successor. Car Fleet holds leader arrival times. Same index-stack idea; different payload. Do not re-solve them on this prompt.
  • Trapping rain water. Same histogram of bars, different question: water on top of each index, not one rectangle under the skyline. That writeup lives under arrays — Trapping Rain Water. Do not solve it here.
  • Pop on <= instead of <. Equal bars close immediately; the wider plateau is credited to the bar that stays. Same O(n) if you are consistent. Mixing the two rules double-counts or drops a plateau.
  • Flush after the loop. Loop i from 0 to n - 1 only, then pop leftovers as if i == n. Same widths. The sentinel-in-loop version is one code path.
  • Maximal rectangle in a binary matrix. Each row becomes a histogram of consecutive 1s, then this method. New prompt. Do not rewrite this method into that one.

You are done with this problem when you can walk [2, 1, 5, 6, 2, 3] out loud, pop 6 then 5 at index 4 for area 10, flush the sentinel for areas 8 and 6, and say why a stack of heights cannot return the widths.