Count Submatrices With All Ones

Given an m x n binary matrix, return the number of submatrices that have all ones.

This is LeetCode 1504: Count Submatrices With All Ones. It asks you to count every possible rectangular region in the matrix where every cell is a 1. Not just the largest one, not just the square ones, but all of them.

Why this problem matters

Counting all-ones submatrices teaches you a pattern that shows up repeatedly in matrix problems: reducing a 2D question to a 1D scan. Instead of brute-forcing every possible rectangle, you precompute information along one axis (consecutive 1s to the left) and then sweep along the other axis (upward expansion). This same "compress one dimension, scan the other" idea appears in problems like Maximal Rectangle and Maximal Square.

It also forces you to think carefully about counting without duplicates. Every submatrix is anchored by exactly one bottom-right corner, so iterating by bottom-right corner gives you a clean partition of the answer.

The key insight

The brute-force approach tries every pair of corners and checks whether all cells inside are 1. That is far too slow.

The insight is to split the work into two phases:

1. For each cell (i, j), compute width[i][j], the number of consecutive 1s ending at column j in row i (including the cell itself). If the cell is 0, this value is 0.
2. For each cell (i, j) as the bottom-right corner of a submatrix, expand upward row by row. As you move up, keep a running minimum of the width values. At each row you reach, the running minimum tells you how many submatrices of that height have their bottom-right corner at (i, j).

By summing these contributions over every cell, you get the total count without checking any cell twice.

The solution

def numSubmat(mat):
    m, n = len(mat), len(mat[0])
    width = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                width[i][j] = (width[i][j - 1] + 1) if j > 0 else 1

    result = 0

    for i in range(m):
        for j in range(n):
            if width[i][j] == 0:
                continue
            min_width = width[i][j]
            for k in range(i, -1, -1):
                min_width = min(min_width, width[k][j])
                if min_width == 0:
                    break
                result += min_width

    return result

How it works

The first double loop builds the width table. For each row, you scan left to right. If a cell is 1, its width is one more than the cell to its left. If it is 0, the width resets to 0. This takes O(m * n) time.

The second part is where the counting happens. For each cell (i, j), you treat it as the bottom-right corner. You walk upward from row i to row 0, tracking the minimum width seen so far. At each row k, min_width tells you how many valid submatrices of height (i - k + 1) end at (i, j). You add min_width to the result.

If the minimum width ever drops to 0, you stop early because no taller rectangle can include that row.

Visual walkthrough

Let's trace through the algorithm on our 3x3 example. The width table and the upward expansion make the counting mechanical.

For the full matrix, the width table is:

1  0  1
1  1  2
1  2  3

Processing each cell as the bottom-right corner and summing the upward contributions gives a total of 22 submatrices.

Complexity analysis

The width-plus-expansion approach visits each cell once to build the table, then for each cell expands upward through at most m rows. That gives O(m^2 * n) total. For most practical inputs this is fast enough. If you need O(m * n), you can replace the inner upward loop with a monotone stack, but that adds significant complexity for the same asymptotic constant.

Building blocks

This problem relies on two core patterns.

1. Prefix accumulation along a row. The width table is a form of prefix computation: for each cell, you accumulate a running count of consecutive 1s. This same idea appears when computing prefix sums, running maximums, or histogram heights row by row.

2. Fixing one corner and sweeping. By anchoring the bottom-right corner and expanding upward, you reduce a 2D counting problem to a 1D sweep. This technique shows up in Maximal Rectangle (where you build histogram heights per row and use a stack) and in problems like Number of Submatrices That Sum to Target (where you fix two row boundaries and sweep columns).

Edge cases

• All zeros: every width value is 0, so the inner loop never fires. Return 0.
• All ones: the width table grows from 1 to n across each row. The answer is the sum of min_width contributions, which equals m*(m+1)/2 * n*(n+1)/2.
• Single row: the upward expansion only ever processes one row, so each cell contributes exactly its width value. The answer is the sum of width[0][j] for all j.
• Single column: each cell's width is either 0 or 1. The upward expansion counts consecutive 1s in the column, giving k*(k+1)/2 for each maximal run of length k.
• Sparse matrix with isolated 1s: each isolated 1 contributes exactly 1 to the total. No expansion reaches neighboring cells.
• Matrix with one 0 in the middle: the 0 forces min_width to drop to 0 during upward expansion, cutting off taller rectangles that would otherwise span across it.

From understanding to recall

The algorithm has two clean phases: build the width table, then expand upward from each cell. The logic is simple once you see it. But reproducing it under time pressure requires you to remember the details: how to initialize the width table, why you take the running minimum during the upward sweep, and why the sum of those minimums gives the total count.

Spaced repetition locks these details in. You write the solution from scratch a few days later, then again a week after that. By the third rep, the two-phase pattern feels natural. You see a matrix counting problem and you immediately think "prefix along one axis, sweep along the other."

This "compress and sweep" approach is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more efficient than solving random problems and hoping the patterns stick.

Related posts

• Maximal Square - DP on a binary matrix to find the largest all-ones square, using a different recurrence but the same 2D thinking
• Set Matrix Zeroes - Another matrix transformation problem that teaches in-place row and column marking
• Unique Paths - The simplest 2D grid DP, building intuition for row-by-row table filling