DSA sheet · Stack · Monotonic stack pattern

Largest Rectangle in Histogram

LeetCode marks this one Hard, but the teacher's promise is that it isn't, once you see the idea. She first builds a brute force (fix a start bar, stretch to the right, keep the minimum height), shows why it gets TLE, explains why two pointers and sliding window don't fit, and then solves it with an increasing monotonic stack plus a zero-height bar at the end.

Why it matters: the area of the best rectangle "standing on" a bar is decided by the nearest smaller bar on its left and the nearest smaller bar on its right. That one fact powers this problem and Maximal Rectangle (problem 9), which reuses this code row by row.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (stack, monotonic stack)
• Part A · Brute force: fix the start, stretch right
• Part A½ · Why not two pointers or sliding window?
• Part B · Optimal: increasing monotonic stack
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates: you only touch the top. The last plate put on is the first one taken off: LIFO (Last In, First Out).

We draw a stack left = bottom, right = top. Both append and pop() are O(1).

Monotonic stack: what it is and what it remembers

A monotonic increasing stack keeps its items in increasing order from bottom to top. When a new item comes that is smaller than the top, we pop the top (and maybe more) until the order is fine again, then push the new item.

The useful part is the moment of popping. When item X is popped because a smaller item Y arrived:

• Y is the next smaller item to the right of X (the first one, otherwise X would have been popped earlier).
• The item just below X in the stack is the previous smaller item on X's left, because the stack is increasing.

So at the moment of the pop, we know both neighbours that "limit" X. That's exactly what this problem needs.

We store indexes in the stack, not heights. From an index we can always read the height (heights[idx]), and the index is what we need for the width.

Part A · Brute force: fix the start, stretch right

LeetCode 84

1The question in simple words

You get heights: the heights of bars in a histogram (a bar chart where the bars stand next to each other with no gaps). Every bar is 1 unit wide. Find the area of the largest rectangle you can draw inside the bars.

 6 |          ██
 5 |       ██ ██
 4 |       ██ ██
 3 |       ██ ██    ██
 2 | ██    ██ ██ ██ ██
 1 | ██ ██ ██ ██ ██ ██
   +------------------
      2  1  5  6  2  3   height
      0  1  2  3  4  5   index

A rectangle covering several bars can only be as tall as the shortest of them, because it must fit inside every bar. Bars 5 and 6 together: height min(5, 6) = 5, width 2, area 10. That's the answer here.

 6 |          ██
 5 |       ▓▓ ▓▓
 4 |       ▓▓ ▓▓
 3 |       ▓▓ ▓▓    ██
 2 | ██    ▓▓ ▓▓ ██ ██
 1 | ██ ██ ▓▓ ▓▓ ██ ██          ▓▓ = the best rectangle, 5 × 2 = 10

Area of a rectangle = height × width. Width of bars from index i to index j (both included) = j − i + 1.

2What the constraints tell us

• 1 ≤ n ≤ 10⁵. The teacher reads this first. An O(n²) solution would do about 10¹⁰ steps. Her rule of thumb: around 10⁸ is safe if the work per step is light, and beyond about 10⁹ you will surely get TLE. So O(n²) is out; we need about O(n) or O(n log n).
• 0 ≤ heights[i] ≤ 10⁴. The biggest possible area is 10⁴ × 10⁵ = 10⁹, which still fits in a normal 32-bit int. Heights can be 0; a 0 bar breaks every rectangle that crosses it.

3Intuition: try every starting bar

Stand on a bar and say "my rectangle starts here". Now walk to the right one bar at a time. As you go, the rectangle gets wider by 1 each step, but its height can only stay the same or get lower: it's the minimum of all bars seen so far. At each step, compute the area and keep the best one.

The teacher points out you can do it in either direction: start at a bar and stretch right, or stand at a bar and look back to the left. Both try every pair (start, end). She codes the "stretch right" version.

4Building the logic from her walk-through

She walks through [2, 1, 5, 6, 2, 3] by hand:

• Start at 2 (index 0): alone, area 2 × 1 = 2. Add the 1: the minimum drops to 1, width 2 → area 2. From now on, because a 1 sits in between, no matter how tall the later bars are, the height stays 1. Width 3 → 3, width 4 → 4, … width 6 → 6. Best so far: 6.
• Start at 1: the height is 1 the whole way: areas 1, 2, 3, 4, 5. Nothing beats 6.
• Start at 5: 5 alone → 5. Add 6 → min 5, width 2 → 10, new best. Add 2 → min 2, width 3 → 6. Add 3 → min still 2, width 4 → 8.
• Start at 6: 6, then min 2 × 2 = 4, then 2 × 3 = 6.
• Start at 2 (index 4): 2, then 2 × 2 = 4. Start at 3: 3.

Final answer: 10. Notice the two things we keep while stretching: the running minimum height and the width j − i + 1.

5Approach steps

1. max_area = 0.
2. For every start i: set h = heights[i].
3. For every end j from i to n − 1: h = min(h, heights[j]); width = j − i + 1; area = h × width; update max_area.
4. Return max_area.

6Code (Python)

class Solution:
    def largestRectangleArea(self, heights):
        n = len(heights)
        max_area = 0
        for i in range(n):                 # the rectangle starts at bar i
            h = heights[i]                 # running minimum height
            for j in range(i, n):          # ...and ends at bar j
                h = min(h, heights[j])     # must fit under every bar
                width = j - i + 1
                max_area = max(max_area, h * width)
        return max_area

7Code line by line

8Dry run: [2, 1, 5, 6, 2, 3]

Each row is one start i. The cells show the area for j = i, i+1, … (running min × width).

9Complexity & remember

• Time O(n²): for start i the inner loop runs n − i times: n + (n−1) + … + 1 ≈ n²/2. With n = 10⁵ that's about 10¹⁰ → TLE. The teacher submits it and shows the TLE.
• Space O(1): just a few variables.

Part A½ · Why not two pointers or sliding window?

When optimising, the teacher runs through the patterns she knows: two pointers, sliding window, stack. Two pointers looks tempting because Container With Most Water and Trapping Rain Water also deal with bars and areas.

Why two pointers fails

In Trapping Rain Water, the water above a bar depends on the tallest bar to its left and right, and the smaller of those decides the level. Once we've used a pointer's bar, we move past it and never need it again. Two pointers works because we can safely throw bars away.

Here we can't. Even a short bar can make the biggest rectangle if it's wide enough. Her example: picture 1, 2, 1, 2, 1, 2, … repeated over many bars. The two tall bars 5 and 6 give only 10, but a height-1 rectangle across 13 bars gives 13. So every bar might be the height of the answer, and none can be thrown away early.

Why sliding window fails

A sliding window needs a rule like "grow the window while it's valid, shrink when it breaks". Here there's no such rule: adding a bar can make the area go up or down, and shrinking the window can too. Nothing tells us which end to move.

Why a stack fits

The area always depends on the minimum height, so we need "the nearest smaller bar" on each side. And her stack signal: whenever you're at a point and keep going back (or forward) to find a smaller or larger value, keep those values in a stack instead. That turns O(n²) into O(n).

Part B · Optimal: increasing monotonic stack

1The question (same)

Same input and output as Part A. Only the method changes.

2What the constraints tell us

n up to 10⁵ → we need O(n). Each bar should be pushed once and popped once.

3Intuition: each bar's own rectangle

Flip the brute force around. Instead of "where does the rectangle start?", ask: "if bar k is the shortest bar in the rectangle, how wide can it be?"

It can spread left and right until it hits a bar shorter than itself. Taller bars are fine (the rectangle fits under them). So:

area(k) = heights[k] × (NSE(k) − PSE(k) − 1)

where PSE = index of the previous smaller bar (−1 if none) and NSE = index of the next smaller bar (n if none). The answer is the biggest area(k) over all bars, because the best rectangle has some shortest bar, and that bar's area(k) is at least as big.

PSE and NSE for every bar of [2, 1, 5, 6, 2, 3]

The biggest is 10 ✓. The stack finds every PSE and NSE in a single pass, at the moment it pops.

4Building the stack rules, the way the teacher does

Rule 1: keep pushing while bars get taller

Heights 2, 3, 4… keep going up: push them all. We can't finish any of them yet, because we don't know where they end on the right.

Rule 2: a shorter bar arrives → pop and compute

When bar j is shorter than the top, the top bar now knows both its limits:

• right smaller = j, the current bar;
• left smaller = the index under it in the stack (call it i).

The bars strictly between i and j are all at least as tall as the popped bar. The width is the count of bars between i and j, with both ends excluded. The teacher derives it from the usual j − i + 1 and then subtracts 2 because neither i nor j is part of the rectangle: j − i + 1 − 2 = j − i − 1.

Rule 3: the stack is empty after the pop → there's no left smaller

Her example: index 0 (height 2) is popped when 1 arrives at j = 1. There's nothing under it. No smaller bar on the left means the rectangle reaches all the way to index 0, so the width is just j (bars 0 … j−1). Here width 1, area 2.

Why popping is safe: the stack throws away bars that can't help any more

Once 1 arrives after 2, the 2 can never be the height of a rectangle that reaches further right: the 1 is in the way. Its rectangle is already final, so we compute it and drop it. In the brute force we kept re-checking such bars; the stack drops them right away. That's where the speed comes from. After popping, the stack still goes up from bottom to top: an increasing monotonic stack.

Rule 4: bars left at the end → add a zero-height bar

After the last real bar, the stack may still hold bars (in the example: heights 1, 2, 3). Nobody smaller came to pop them. The teacher's trick: pretend there is one extra bar of height 0 at index n. Every real bar is ≥ 0, and it's popped only when something strictly smaller arrives… a 0 is smaller than every positive bar, so it pops them all and computes their areas with j = n.

5Approach steps

1. Empty stack of indexes; max_area = 0.
2. For i from 0 to n (n means the fake 0 bar): h = 0 if i == n else heights[i].
3. While the stack isn't empty and h < height of the top: pop the top → its height; width = i if the stack is now empty, else i − (new top) − 1; update max_area.
4. Push i.
5. Return max_area.

6Code (Python)

class Solution:
    def largestRectangleArea(self, heights):
        n = len(heights)
        max_area = 0
        st = []                                  # indexes, heights increasing
        for i in range(n + 1):                   # i == n is the fake 0 bar
            h = 0 if i == n else heights[i]
            while st and h < heights[st[-1]]:   # bar i is the right smaller
                height = heights[st.pop()]       # the bar we finish now
                width = i if not st else i - st[-1] - 1
                max_area = max(max_area, height * width)
            st.append(i)
        return max_area

7Code line by line

8Dry run: [2, 1, 5, 6, 2, 3]

The stack is shown as index(height), left = bottom, right = top.

The teacher calls the bar 2 at index 4 "magic": when the 0 pops it, its left smaller is index 1 and its right smaller is index 6, so the stack tells us it spans width 4 (indexes 2 to 5) and gives area 8, even though bars 5 and 6 left the stack long ago. And the 1 at the bottom, popped last with an empty stack, spans the whole array: 1 × 6 = 6.

 6 |          ██
 5 |       ██ ██
 4 |       ██ ██
 3 |       ██ ██    ██
 2 | ██    ▓▓ ▓▓ ▓▓ ▓▓          bar 4 (height 2): PSE = 1, NSE = 6
 1 | ██ ██ ▓▓ ▓▓ ▓▓ ▓▓          width 6 − 1 − 1 = 4, area 8

9Complexity & remember

• Time O(n). There's a while inside a for, but every index is pushed once and popped at most once. Worst case, all bars increase: n pushes, then the fake 0 does n pops. That's O(n) + O(n) = O(2n) = O(n), instead of O(n²). Her tip: if it doesn't feel linear, dry-run it and count what gets popped at each i; the total is never more than n.
• Space O(n): the stack can hold every index (increasing input).

Part C · Revision page

s = Solution()
print(s.largestRectangleArea([2, 1, 5, 6, 2, 3]))   # 10
print(s.largestRectangleArea([2, 4]))               # 4
print(s.largestRectangleArea([5]))                  # 5
print(s.largestRectangleArea([1, 2, 3, 4, 5]))      # 9
print(s.largestRectangleArea([3, 3, 3]))            # 9
print(s.largestRectangleArea([2, 0, 2]))            # 2

Based on this video: Largest Rectangle in Histogram | Monotonic Stack