Largest Rectangle in Histogram

Learning goal: Translate a histogram into a maximum-area rectangle problem and identify what makes a candidate rectangle valid.

Core idea A rectangle spanning several consecutive bars can be no taller than the shortest bar in that span. Therefore, every bar is a natural candidate for the rectangle's limiting height. If we can discover how far that bar extends left and right before a shorter bar blocks it, we can compute its best possible area.

Algorithm plan

• Treat each bar as the shortest bar of a candidate rectangle.
• Find the nearest strictly shorter bar on the left and right.
• Use those boundaries to calculate the bar's widest valid width.
• Keep the largest area seen.

Micro-example For [2,1,5,6,2,3], bar 5 can extend across indices 2..3 but stops before height 2 at index 4. Its area is 5 * 2 = 10.

Pitfalls

• A rectangle must use consecutive bars; gaps are not allowed.
• The height is the minimum bar in the selected range, not necessarily an endpoint.
• Equal heights need a consistent stack policy so they are not processed redundantly.

Recap

• Every bar can define a maximum-width rectangle.
• Shorter bars determine the boundaries.
• The goal is to compute all useful bar areas efficiently.

Learning goal: Understand why an increasing stack stores exactly the indices needed to find rectangle boundaries.

Core idea Scan bars from left to right while maintaining indices whose heights are in increasing order. A new shorter bar proves that every taller bar on top of the stack has just found its first shorter bar on the right. The element remaining below a popped index is its first shorter boundary on the left.

Algorithm plan

• Push an index when its height keeps the stack increasing.
• When the current height is smaller than the stack top, pop that taller index.
• Let right = i and left = stack[-1] after the pop.
• The valid width is right - left - 1.
• Repeat popping before pushing the current index.

Micro-example Suppose the stack is [1,2,3] with heights [1,5,6], and index 4 has height 2. Popping index 3 leaves 2, so its width is 4 - 2 - 1 = 1.

Pitfalls

• Do not use the stack top before popping as the left boundary.
• The current index is excluded because its height is shorter.
• The new stack top is also excluded because it is shorter than the popped bar.

Recap

• The stack is increasing by height.
• A shorter bar triggers area calculations.
• After a pop, width is currentIndex - newStackTop - 1.

Learning goal: Turn the stack invariant into a complete one-pass algorithm.

Core idea Each index is pushed once and popped at most once. That makes the total stack work linear, even though one loop iteration may pop several bars. Appending a sentinel height of 0 guarantees that every remaining bar is eventually popped and evaluated.

Algorithm plan

Micro-example At index 4 in [2,1,5,6,2,3], height 2 pops heights 6 and 5. The second pop uses left boundary index 1, giving width 4 - 1 - 1 = 2 and area 5 * 2 = 10.

Pitfalls

• Do not forget the sentinel; otherwise increasing bars at the end remain unprocessed.
• Use the popped bar's height, not the current shorter height, in the area formula.
• Decide whether equal heights should replace or coexist; the strict increasing version is enough here.

Recap

• Scan once with an increasing index stack.
• Pop when a shorter bar closes rectangles.
• The sentinel flushes all unfinished candidates.

Learning goal: Trace every push and pop while observing how rectangle widths are derived.

Core idea The stack contains indices of bars that are still waiting for a shorter bar on the right. While heights rise, no rectangle closes, so indices accumulate. When height 2 arrives at index 4, it closes both the height-6 and height-5 candidates, revealing two different widths.

Algorithm plan

• Push 0, then pop it when height 1 arrives.
• Build the increasing stack [1,2,3] through heights 1,5,6.
• At index 4, pop 3 and then 2.
• Push 4, then 5.
• Process sentinel index 6 to flush the remaining stack.

Micro-example Popping index 2 at current index 4 leaves index 1 below it. Thus the rectangle spans indices 2..3, with width 4 - 1 - 1 = 2 and area 5 * 2 = 10.

Pitfalls

• Index 4 is a boundary, so it is not included in the height-5 rectangle.
• Index 1 is also a boundary after the pop, so the rectangle cannot extend across it.
• The final sentinel is not a real histogram bar; it only forces cleanup.

Recap

• The best area appears when index 2 is popped.
• Stack boundaries encode the maximal valid span.
• The final answer for this example is 10.

Learning goal: Avoid the boundary and cleanup mistakes that most often break monotonic-stack solutions.

Core idea The stack does not directly store rectangle widths; it stores possible left boundaries. Width is determined only after a bar is popped, because only then are both shorter boundaries known. The most important detail is that both the current index and the new stack top are excluded from the span.

Algorithm plan

• On a pop, save the popped index j.
• Set right = i, the current shorter index.
• Set left = stack[-1] after popping, or -1 if empty.
• Compute width = right - left - 1.
• Use heights[j] * width to update the answer.

Micro-example When index 2 is popped at i = 4, the stack becomes [1]. The span is from index 2 through 3, not through index 4 and not back through index 1; its width is 4 - 1 - 1 = 2.

Pitfalls

• Using i - poppedIndex incorrectly ignores the wider span revealed by the new stack top.
• Forgetting to subtract 1 includes a shorter boundary.
• Omitting the sentinel misses rectangles at the right edge.
• Empty-stack handling requires a virtual left boundary of -1.

Recap

• Pop first, then read the new stack top.
• Both boundaries are exclusive.
• Sentinel zero handles increasing suffixes.

Learning goal: Justify the linear complexity and recognize when this pattern applies.

Core idea Although the inner loop can pop many indices during one iteration, each index enters the stack once and leaves it once. The total number of stack operations is therefore at most proportional to n. The stack trades extra memory for immediate access to the nearest unresolved boundary.

Algorithm plan

• Scan the original bars plus one sentinel: O(n) iterations.
• Charge each push to one index and each pop to that same index.
• Compute every popped bar's area in constant time.
• Store at most n indices in the stack.

Micro-example For [2,1,5,6,2,3], there are six real pushes and six corresponding opportunities to pop. No bar is repeatedly pushed, so the work grows linearly rather than quadratically.

Pitfalls

• Do not conclude O(n^2) merely because a loop is nested inside another loop.
• The stack can contain all indices for an increasing histogram, so space is O(n).
• The sentinel is an implementation convenience and does not change asymptotic bounds.

Recap

• Time complexity: O(n).
• Auxiliary space: O(n).
• The reusable pattern is: maintain unresolved candidates until a smaller value reveals their boundaries.