DSA sheet · Stack · Monotonic stack pattern

Maximal Rectangle

This is the last question of the monotonic stack pattern, and the teacher says up front that its prerequisite is Largest Rectangle in Histogram (problem 6). She first writes a brute force that tries every rectangle (corner to corner) and checks it cell by cell, shows the huge complexity and the TLE, explains why a graph approach (BFS/DFS) isn't the right tool, and then shows the real trick: treat each row as the floor of a histogram, and run the histogram solution once per row.

Why it matters: it's a perfect example of reducing a new problem to one you already solved. A 2D matrix looks scary; broken into rows, it's just problem 6 again.

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, the histogram solution)
• Part A · Brute force: every pair of corners, check every cell
• Part B · Optimal: one histogram per row + 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. Last in, first out: LIFO.

Drawn left = bottom, right = top. Always check that the stack is not empty before pop() or st[-1].

Monotonic increasing stack (from problem 6)

We keep bar indexes in the stack so that their heights increase from bottom to top. When a shorter bar arrives, we pop the taller ones. At the moment a bar is popped:

• the current bar is its next smaller on the right (NSE);
• the bar under it in the stack is its previous smaller on the left (PSE), or there's none if the stack is empty.

The biggest rectangle whose shortest bar is the popped bar spans everything between PSE and NSE: width = NSE − PSE − 1 (or NSE if there's no PSE). A fake bar of height 0 at the end pops whatever is left.

def largest_rectangle_area(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]]:
            height = heights[st.pop()]
            width = i if not st else i - st[-1] - 1
            max_area = max(max_area, height * width)
        st.append(i)
    return max_area

If any of this feels new, read problem 6 first; the teacher insists on it too.

Part A · Brute force: every pair of corners, check every cell

LeetCode 85

1The question in simple words

You get a grid (matrix) of "1"s and "0"s. Find the biggest rectangle that contains only 1s, and return its area (the number of cells in it).

        col: 0 1 2 3 4
  row 0:     1 0 1 0 0
  row 1:     1 0 1 1 1
  row 2:     1 1 1 1 1
  row 3:     1 0 0 1 0          answer = 6  (rows 1–2, cols 2–4)

The teacher points at several valid rectangles of all-1s, with areas 2, 4, 5 and 6; the biggest is 6. A block that would include even one 0 is not allowed: for example, extending the red block down into row 3 hits zeros, so it's invalid.

On LeetCode the cells are the characters "1" and "0", not numbers, so we compare with "1".

2What the constraints tell us

• 1 ≤ rows, cols ≤ 200. The grid has at most 200 × 200 = 4 × 10⁴ cells. Call that number of cells N.
• The teacher's reading: an O(N²) idea would be about 1.6 × 10⁹, borderline at best, so we should aim lower. Her limits again: past about 10⁸ it gets slow; past about 10⁹ it's TLE.
• Both sizes are at least 1, so the matrix is never empty.

3Intuition: a rectangle is fixed by two corners

Any rectangle in a grid is decided by its top-left cell (r1, c1) and its bottom-right cell (r2, c2). So the simplest idea is: try every top-left, try every bottom-right below and to the right of it, and check whether every cell inside is 1. If yes, compute the area and keep the biggest.

Two conditions make a valid answer: (1) it must be a rectangle (not an L-shape or any other shape), which the two-corner idea guarantees, and (2) every cell inside must be 1.

4Building the logic from examples

Area from two corners: why "+1"?

Start with the smallest case: (r1, c1) = (r2, c2) = (0, 0). That's one cell, area 1. The formula has to give 1 here, not 0.

The teacher's explanation: on a number line, the distance from point 1 to point 1 is 1 − 1 = 0, because we measure between points. In a grid we count cells, and the cells from r1 to r2 (both included) number r2 − r1 + 1.

area = (r2 − r1 + 1) × (c2 − c1 + 1)

For (0,0) → (0,0): 1 × 1 = 1 ✓. For (1,2) → (2,4): 2 × 3 = 6 ✓.

Growing the bottom-right corner

Fix the top-left at (0, 0). Move the bottom-right: (0,0) is valid (area 1). (0,1) includes a 0 → invalid. Then (1,0): cells (0,0) and (1,0) are both 1 → valid, area 2. Then (1,1) → the block from (0,0) to (1,1) includes zeros → invalid. And so on. For each pair we re-check all cells inside with two more loops.

5Approach steps

1. For every top-left (r1, c1): if that cell is 0, skip it.
2. For every bottom-right (r2, c2) with r2 ≥ r1 and c2 ≥ c1:
3. Check every cell in rows r1..r2, columns c1..c2. If any is 0, this rectangle is invalid.
4. If it's valid: area = (r2 − r1 + 1) × (c2 − c1 + 1); update the maximum.
5. Return the maximum.

6Code (Python)

class Solution:
    def maximalRectangle(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        max_area = 0
        for r1 in range(rows):                       # top-left corner
            for c1 in range(cols):
                if matrix[r1][c1] == "0":            # can't start on a 0
                    continue
                for r2 in range(r1, rows):           # bottom-right corner
                    for c2 in range(c1, cols):
                        if self.allOnes(matrix, r1, c1, r2, c2):
                            area = (r2 - r1 + 1) * (c2 - c1 + 1)
                            max_area = max(max_area, area)
        return max_area

    def allOnes(self, matrix, r1, c1, r2, c2):
        for r in range(r1, r2 + 1):
            for c in range(c1, c2 + 1):
                if matrix[r][c] == "0":
                    return False                     # one 0 spoils it
        return True

7Code line by line

8Dry run: a few rectangles from the example

After all pairs, the answer is 6 ✓.

9Complexity & remember

• Time O((R·C)³): R·C choices for the top-left × R·C for the bottom-right × up to R·C cells to check. All three are nested. With R·C = 4 × 10⁴, that's (4 × 10⁴)³ = 64 × 10¹² → TLE. The teacher runs it (correct on the samples) and then submits it to show the TLE.
• Space O(1).

Part B · Optimal: one histogram per row + monotonic stack

1The question (same)

Same grid, same answer. We change how we look at the grid.

2What the constraints tell us

R, C ≤ 200. If each row costs O(C) after O(C) preparation, the total is O(R·C) = 4 × 10⁴. Tiny.

3Intuition: first, why not a graph?

The teacher admits that the first time she saw this problem she thought of graphs. A 2D grid can be seen as a graph (each cell is a node, neighbours are joined), and "Max Area of Island" uses BFS/DFS to measure connected groups of 1s.

But BFS/DFS finds a connected blob of any shape. In the example, all the 1s touch each other, so BFS would report the whole blob, which is not a rectangle. You'd need extra logic to check rectangle shapes, and it would be slower. So she drops the graph idea.

Then why a stack? Nothing in the grid obviously says "go back and find a smaller value". The trick is to stop seeing a matrix and look at it row by row.

4Building the logic: turn each row into a histogram

Just row 0

Look only at row 0: 1 0 1 0 0. Think of each 1 as a block of height 1 standing on the floor. That's a histogram with heights [1, 0, 1, 0, 0]. The largest rectangle is 1.

Rows 0–1, with row 1 as the floor

Now stand on row 1 and look up. In each column, count how many 1s are stacked on top of each other, ending at row 1. Column 0 has 1 and 1 → height 2. Column 1 has a 0 at row 1 → height 0. Column 2 → 2. Columns 3 and 4 have a 1 only in row 1 → 1. Heights: [2, 0, 2, 1, 1]. Largest rectangle: the three bars 2, 1, 1 at columns 2–4 give height 1 × width 3 = 3 (and single bars give 2).

The teacher's point: problem 6 also just took an array like [2, 0, 2, 1, 1]; the blocks were only a picture. So if we can turn the 2D grid into a 1D heights array for each row, we can reuse problem 6 directly.

Rows 0–2, floor = row 2

Heights become [3, 1, 3, 2, 2]. The largest rectangle here is height 2 × width 3 = 6. That's our answer.

Floor = row 3, and the rule for zeros

Row 3 is 1 0 0 1 0. You might think "just keep adding", but that would be wrong. A 1 counts only if it's directly on top of other 1s with no gap. If the floor cell is 0, nothing above it can reach the floor, so that column's height drops back to 0. Heights: [4, 0, 0, 3, 0]. Largest: 4. That's less than 6.

The answer is the biggest of the four: 6.

 1 | ██    ██
   +---------------
      1  0  1  0  0

 2 | ██    ██
 1 | ██    ██ ██ ██
   +---------------
      2  0  2  1  1

 3 | ██    ██
 2 | ██    ▓▓ ▓▓ ▓▓
 1 | ██ ██ ▓▓ ▓▓ ▓▓
   +---------------
      3  1  3  2  2

 4 | ██
 3 | ██       ██
 2 | ██       ██
 1 | ██       ██
   +---------------
      4  0  0  3  0

▓▓ = the best rectangle (2 × 3 = 6). In the grid it's rows 1–2, columns 2–4.

5Approach steps

1. heights = [0] × cols; max_area = 0.
2. For each row i, for each column j: if the cell is "1", heights[j] += 1, else heights[j] = 0.
3. After finishing the row, run the histogram helper on heights and update max_area.
4. Return max_area.

6Code (Python)

class Solution:
    def maximalRectangle(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        heights = [0] * cols          # 1s stacked up to the current row
        max_area = 0
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "1":
                    heights[j] += 1   # one more block on this column
                else:
                    heights[j] = 0    # a 0 breaks the column
            max_area = max(max_area, self.largestRectangleArea(heights))
        return max_area

    def largestRectangleArea(self, heights):     # problem 6, unchanged
        n = len(heights)
        max_area = 0
        st = []
        for i in range(n + 1):
            h = 0 if i == n else heights[i]
            while st and h < heights[st[-1]]:
                height = heights[st.pop()]
                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: the stack on floor row 2, heights [3, 1, 3, 2, 2]

Previous smaller and next smaller for every bar

The stack, step by step

The whole matrix, row by row

9Complexity & remember

• Time O(R × C). Updating heights is C steps per row. The helper is O(C) per row: its while loop is not nested work, because each index is pushed once and popped at most once (O(2C)). So each row costs O(C), and R rows cost O(R·C) ≈ 4 × 10⁴.
• Space O(C): the heights list (reused for every row) plus the helper's stack.

Part C · Revision page

m = [["1","0","1","0","0"],
     ["1","0","1","1","1"],
     ["1","1","1","1","1"],
     ["1","0","0","1","0"]]
s = Solution()
print(s.maximalRectangle(m))                 # 6
print(s.maximalRectangle([["0"]]))           # 0
print(s.maximalRectangle([["1"]]))           # 1
print(s.maximalRectangle([["1"],["0"],["1"]]))   # 1
print(s.maximalRectangle([["1","1"],["1","1"]]))  # 4

Based on this video: Maximal Rectangle | Monotonic Stack