p54 — Largest Rectangle in Histogram

Source: LeetCode 84 · Hard · Topics: Array, Stack, Monotonic Stack Companies (2024–2025 frequency): Google (very high), Meta (high), Amazon (high), Microsoft (medium-high), Bloomberg (medium-high), HFT firms (high) Loop position: The classic “monotonic stack Hard.” If you can derive the algorithm (not just memorize it), you understand monotonic stacks. Direct precursor to LC 85 Maximal Rectangle.

1. Quick Context

Given heights[] (non-negative ints), find the area of the largest axis-aligned rectangle whose top sits on or below the histogram and whose bottom is on the x-axis.

The key reframing:

For each bar i, what is the maximal-width rectangle whose height is exactly heights[i]? Its width spans from the first bar to the LEFT that’s strictly shorter, to the first bar to the RIGHT that’s strictly shorter.

So area-with-bar-i-as-the-minimum = heights[i] * (right_smaller[i] - left_smaller[i] - 1).

The answer = max over all i.

Computing left_smaller[i] and right_smaller[i] is two monotonic-stack passes — or one with a sentinel.

Two-pass version (intuitive)

n = len(heights)
left  = [-1] * n   # index of previous strictly smaller (or -1 sentinel)
right = [n]  * n   # index of next     strictly smaller (or n  sentinel)

stack = []                                  # increasing heights
for i in range(n):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    left[i] = stack[-1] if stack else -1
    stack.append(i)

stack = []
for i in range(n - 1, -1, -1):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    right[i] = stack[-1] if stack else n
    stack.append(i)

return max(heights[i] * (right[i] - left[i] - 1) for i in range(n))

One-pass version (sentinel + resolve-on-pop)

heights = heights + [0]   # sentinel forces final flush
stack = []                # indices, heights STRICTLY INCREASING
best = 0
for i, h in enumerate(heights):
    while stack and heights[stack[-1]] > h:
        top = stack.pop()
        # width spans (prev-smaller-than-top, i) exclusive on both ends
        left = stack[-1] if stack else -1
        best = max(best, heights[top] * (i - left - 1))
    stack.append(i)
return best

Both O(n).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/largest-rectangle-in-histogram/

STOP. 20-min timer. Don’t peek.

3. Prerequisite Concepts

• Monotonic stack (p51 / p52 / p53).
• The “for each element, find left and right neighbors satisfying a condition” pattern.
• Sentinel values (the appended 0 at the end).
• Resolve-on-pop semantics.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: Find max area h * w where h = min(heights[l..r]) and w = r - l + 1, over all 0 ≤ l ≤ r < n.

Step 2 — Clarify:

• “Heights ≥ 0?” (Yes.)
• “Width of each bar = 1?” (Yes.)
• “Can it be 0?” (Yes, gives 0 contribution.)
• “Empty array → 0?” (Yes.)

Step 3 — Constraints: n ≤ 10^5. O(n) or O(n log n) only.

Step 4 — Examples:

• [2,1,5,6,2,3] → 10 (the 5 and 6 form a 5×2 rectangle).
• [2,4] → 4 (the 4 alone, or 2×2 = 4 also).
• [1] → 1.
• [0,0,0] → 0.
• [2,1,2] → 3 (height 1 spans the full width).
• [6,7,5,2,4,5,9,3] → 16 (the 4-5-9 group height 4 spans width 3 from index 4..6… actually compute carefully).

Step 5 — Brute force:

• (a) For each pair (l, r), compute min and area. O(n²) pairs × O(n) min = O(n³).
• (b) For each i, walk left and right while ≥ heights[i]. O(n²).

Step 6 — Complexity target: O(n) via monotonic stack.

Step 7 — Pattern: “For each bar as the minimum of its maximal span” + monotonic stack to find left/right smaller indices.

Step 8 — Develop: see solution.py.

Step 9 — Test: monotone up; monotone down; plateau; valleys; zeros; single bar; LC example.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — The “each bar is the min” reframing

6.1 Why “each bar as the minimum”?

Every rectangle in the histogram has a specific bar that limits its height (one of the bars whose top equals the rectangle’s top; if multiple are tied, any of them works).

So the set of all possible rectangles can be partitioned by “which bar is the limiting one.” For bar i, the largest rectangle limited by it has height heights[i] and width = max span where every bar is ≥ heights[i].

That width = right_smaller[i] - left_smaller[i] - 1 where smaller is STRICT.

Take the max over all i. Done.

6.2 Why STRICT smaller, not ≤?

If two bars have equal height, only ONE of them is the “official” limiting bar for any rectangle that spans both. Using STRICT smaller for both boundaries means: the leftmost equal-height bar “owns” all rectangles of that height. Tied bars on either side don’t truncate the span — they extend it.

Example: [2,1,5,5,2]. For the rectangle of height 5: it should span both 5s for area 5×2 = 10. If we used ≥ for the right-boundary, the right-smaller of the leftmost 5 would be the right 5 (which has the same height), giving width 1 instead of 2.

Convention used in this codebase: left_smaller uses STRICT, right_smaller uses STRICT. Equivalent: left ≤ + right < (or vice versa), but only one side may be non-strict to avoid double-counting. Be careful.

6.3 The one-pass sentinel trick

Appending 0 at the end forces the stack to flush completely (every remaining element gets popped because 0 is smaller than anything). This avoids a separate “drain” loop after the main iteration.

For the LEFT boundary: when popping top, the bar just below it on the stack (stack[-1] after pop) is the previous strictly-smaller (because the stack is monotonically INCREASING, and we popped everything ≥ heights[top] already).

For the RIGHT boundary: i is the current iteration index, which is the next-strictly-smaller for top (we only pop when heights[top] > h).

Width = i - left - 1. Area = heights[top] * width.

6.4 Why the stack is INCREASING here (vs. decreasing in p51)?

We’re popping when a smaller value arrives. The stack therefore holds increasing values (bottom to top is non-decreasing; with strict pop, it’s strictly increasing).

The mental model: “stack of candidates to be the limiting bar; each waits for someone shorter to truncate its span on the right.”

6.5 Two-pass vs one-pass — pick which?

Two-pass: more verbose but conceptually clearer; easier to debug; can be parallelized (left and right are independent).

One-pass with sentinel: shorter; “interview-friendly”; trickier to explain at the whiteboard.

For senior+ signal: start with the two-pass derivation (“here’s left_smaller, here’s right_smaller, then area is straightforward”), then optimize to one-pass at the end. Demonstrates understanding over memorization.

6.6 Divide and conquer (O(n log n) average, O(n²) worst)

Find the index of the minimum bar, compute min_height * n, then recurse on left and right halves. With a sparse-table RMQ for the min, each step is O(1) → O(n log n) average if the min sits roughly in the middle. Worst case (sorted input) is O(n²).

Useful as an alternative when the monotonic stack feels foreign. Worse asymptotically; mention for breadth.

6.7 Connection to LC 85 — Maximal Rectangle in Binary Matrix

For each row of a 0/1 matrix, compute a “heights” histogram = consecutive 1s in each column ending at this row. Run LC 84 on each row → O(rows × cols). Direct application.

6.8 Connection to p55 — Trapping Rain Water

Similar shape (mono-stack on heights), but different operation:

• Histogram: max area below.
• Trap: total water above trapped between higher bars on both sides.

Both have a monotonic stack solution, both have a two-pointer alternative for trap, both have prefix-array alternatives.

7. Anti-Pattern Analysis

1. stack[-1] >= h in both passes → using non-strict on both sides → double-counts tied bars or under-counts.
2. Forget the sentinel 0 at the end of the one-pass version → final tall bars never get popped → wrong answer (often misses the global max).
3. Compute width as right - left instead of right - left - 1 → off-by-one, area too large by heights[top].
4. Brute force O(n²) on n = 10^5 → TLE (10^10 ops).
5. Store heights on the stack instead of indices — you’ll lose the position info you need for width.
6. For each i, expand left and right manually — looks O(n) per bar but is O(n²) overall in the worst case (plateau).
7. Use a max-heap to find tallest first — wrong tool; doesn’t model “as the limiting bar.”
8. Try DP dp[i] = something — there’s no clean DP recurrence here. The stack-based amortization is what gives us O(n).
9. Modify heights in place to add the sentinel without restoring — surprising side effect to caller; copy or append-then-pop.
10. Use for i, h in enumerate(heights + [0]) AND also reference heights[i] inside — heights is the unmodified original; subtle bug. Use h consistently or define H = heights + [0].

8. Skills & Takeaways

• The “each element as the minimum of its maximal range” reframing — applies far beyond this problem.
• Two-pass vs one-pass monotonic stack; sentinel trick for the one-pass form.
• Why strict-on-both-sides (or balanced strict/non-strict) avoids double-counting.
• Connection to LC 85 (binary matrix → histograms) and p55 (Trap).
• Divide-and-conquer alternative as a breadth signal.

9. When to Move On

• You can DERIVE the algorithm (not memorize) starting from the “each bar as the min” reframing in < 15 min.
• You can write the one-pass with sentinel in < 8 min cold.
• You can explain the strict-vs-non-strict trade-off precisely.
• You connect to LC 85 in one sentence.
• Stress test on 500 random arrays (sizes ≤ 30, heights 0..10) agrees with O(n³) brute.

10. Company Context

Google:

• L5/L6 onsite. Often paired with LC 85 as the follow-up.
• Bar Raiser: “Derived the algorithm from first principles; articulated strict-vs-non-strict; mentioned LC 85 generalization.”

Meta:

• L5/L6. Critical for E5+ promo packets. Often the “hard” of a 2-question onsite.

Amazon:

• L6+. Productized: “max contiguous warehouse-aisle capacity.”

Microsoft:

• L65+. Often the second question after a Medium.

Bloomberg:

• HFT/trading SWE. “Max contiguous volume window across N stocks” is the LC 85 generalization.

HFT firms (Jane Street / Citadel / Two Sigma):

• Very high. The interviewer wants to see you derive it, not regurgitate it. They will ask follow-ups about the strict-vs-non-strict edge case.

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Brute O(n²) works correctly.
• Eventually arrives at mono-stack with hints.
• Handles single bar, zeros, plateau.

Senior (L5):

• Derives mono-stack from “each bar as the min.”
• One-pass with sentinel cleanly.
• Articulates strict-vs-non-strict.
• Connects to LC 85.

Staff (L6):

• Two-pass and one-pass variants with trade-off analysis.
• Divide-and-conquer + sparse-table RMQ alternative.
• LC 85 generalization with column-cumulative-heights rolling.
• Discusses parallelization (two-pass left/right independent).

Principal (L7+):

• Discusses streaming version: bars arrive one at a time; maintain “current largest rectangle” — possible but requires care; the stack must be retained.
• Discusses 3D generalization (max axis-aligned box in heightmap) — much harder, not solvable by direct extension.
• Discusses cache-oblivious analysis of the two-pass vs one-pass approaches.
• Discusses persistent stacks for “as of time t, what was the largest rectangle?” queries.

13. Follow-up Q&A

Q1: LC 85 Maximal Rectangle (binary matrix). Sketch. A1: For each row, build heights[c] = consecutive 1s in column c ending at this row (carry from previous row: if matrix[r][c] == 1, heights[c] += 1; else heights[c] = 0). Then run LC 84 on heights. Take max over all rows. O(rows × cols).

Q2: What if bars have different widths? A2: Then “width” isn’t right - left - 1; it becomes sum(width[l+1..r-1]). Use prefix sums of widths for O(1) range-width lookup; algorithm otherwise identical.

Q3: What’s the worst case for stack size? A3: n (strictly increasing input — nothing gets popped until the sentinel triggers the final flush).

Q4: Can you do it in O(1) extra space? A4: Not in general. The stack can be Θ(n). Some in-place encoding tricks exist but are tricky and not worth it.

Q5: What if there are negative heights? A5: Problem definition assumes ≥ 0. With negatives, the area concept breaks (no “below” sense). Typically clarified out of scope.

Q6: How do you handle very large heights that overflow int? A6: In Python, no issue (arbitrary precision). In C++/Java, use long long for area = heights[i] * width since 10^5 * 10^9 ≈ 10^14, overflows 32-bit.

Q7: Divide and conquer with RMQ — when is it preferable? A7: Almost never asymptotically (O(n log n) ≥ O(n)). Preferable conceptually only if you’ve already built an RMQ structure for other queries on the same array.

Q8: Can you parallelize this for huge arrays? A8: The two-pass version: left-smaller and right-smaller passes are independent → run in parallel. Within each pass, parallelization is hard (sequential dependency on the stack). For TRULY huge n, partition into chunks, compute local left_smaller per chunk, then merge boundaries — non-trivial.

14. Solution Walkthrough

See solution.py. Four implementations:

• largest_rectangle_one_pass — sentinel + monotonic increasing stack. O(n).
• largest_rectangle_two_pass — explicit left_smaller and right_smaller arrays. O(n).
• largest_rectangle_each_bar — for each bar, expand left/right manually. O(n²) oracle.
• largest_rectangle_brute — all (l, r) pairs. O(n³) oracle for tiny n.

Stress test on 500 random arrays of size ≤ 20, heights 0..10. All four agree.

15. Beyond the Problem

Principal-engineer code review comment:

“The one-pass-with-sentinel version is elegant but is also the hardest to maintain — six months from now, someone will read i - left - 1 and not remember why it’s -1. The two-pass version is 3× the lines but every loop has an obvious invariant (left[i] = previous strictly-smaller). For an interview, the one-pass shows mastery. For production, prefer the two-pass with comments. The wins of cleverness rarely pay back the cost of confusion when the on-call engineer is debugging at 3 AM.”