LeetCode 1504 - Count Submatrices With All Ones

The problem gives us an m x n binary matrix where each cell contains either 0 or 1. We must count how many rectangular submatrices consist entirely of ones. A submatrix is any contiguous rectangular region inside the matrix.

leetcodemediumarraydynamic-programmingstackmatrixmonotonic-stack

LeetCode Problem 1504

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack

Solution

Problem Understanding

The problem gives us an m x n binary matrix where each cell contains either 0 or 1. We must count how many rectangular submatrices consist entirely of ones.

A submatrix is any contiguous rectangular region inside the matrix. For every possible rectangle, we need to determine whether every element inside it equals 1. If it does, we count it.

For example, consider this matrix:

1 0 1
1 1 0
1 1 0

A valid submatrix could be:

1 1
1 1

because all cells are ones. However, a rectangle containing even a single zero is invalid.

The constraints are important:

  • 1 <= m, n <= 150
  • Total cells are at most 22500

A naive brute force approach that checks every possible rectangle cell by cell becomes too slow because the number of rectangles grows rapidly. We therefore need a more efficient way to count valid submatrices.

Several edge cases are important:

  • A matrix filled entirely with zeros should return 0
  • A matrix filled entirely with ones produces the maximum number of submatrices
  • Single row and single column matrices require careful handling because rectangles degenerate into intervals
  • Alternating zeros and ones can break assumptions about continuity
  • Large dense matrices require an efficient algorithm to avoid timeouts

The key challenge is efficiently determining how many all-ones rectangles end at each position.

Approaches

Brute Force Approach

The brute force solution considers every possible submatrix.

A rectangle can be defined by:

  • Top row
  • Bottom row
  • Left column
  • Right column

For each rectangle, we scan all cells inside it to verify that every value equals 1.

This approach is correct because it explicitly checks every possible candidate rectangle. However, it is computationally expensive.

There are:

  • O(m²) choices for row boundaries
  • O(n²) choices for column boundaries

That already gives O(m² * n²) rectangles. Verifying each rectangle can take up to O(m * n) time.

The total complexity becomes:

O(m³ * n³)

which is far too slow for matrices up to 150 x 150.

Optimal Approach

The key observation is that we can transform the problem into counting rectangles in a histogram.

For each row, we compute a height array:

height[j] = number of consecutive ones ending at current row

Example:

1 0 1
1 1 0
1 1 0

At row 2, the heights become:

3 2 0

This means:

  • Column 0 has height 3
  • Column 1 has height 2
  • Column 2 has height 0

Now the problem becomes:

How many subrectangles end at the current row?

For every column, we want to count how many rectangles use that column as the right boundary.

We use a monotonic increasing stack to efficiently determine contributions from histogram bars. The stack helps maintain previous smaller heights, allowing us to compute rectangle counts in linear time per row.

This reduces the overall complexity to:

O(m * n)

which easily fits the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(m³ * n³) O(1) Enumerates every rectangle and checks all cells
Optimal O(m * n) O(n) Uses histogram heights with a monotonic stack

Algorithm Walkthrough

Step 1: Build Histogram Heights

For each row, maintain an array called heights.

If mat[row][col] == 1:

heights[col] += 1

Otherwise:

heights[col] = 0

This converts the matrix row into a histogram where each bar represents consecutive vertical ones ending at the current row.

Step 2: Count Rectangles in the Histogram

For the current histogram, we count all subrectangles ending at the current row.

We process columns from left to right.

We maintain:

  • A monotonic increasing stack
  • An array dp
  • dp[j] stores the number of valid submatrices ending at column j

Step 3: Maintain a Monotonic Stack

The stack stores column indices with increasing heights.

While the current height is smaller than or equal to the height at the top of the stack, we pop elements.

This ensures:

heights[stack[0]] < heights[stack[1]] < ...

The stack helps find the nearest previous smaller height efficiently.

Step 4: Compute Rectangle Contributions

Suppose the nearest smaller height index is prev.

Then:

dp[j] = dp[prev] + heights[j] * (j - prev)

Why?

Every subarray ending at j can extend from the previous smaller height.

The minimum height across that range determines how many rectangles are possible.

If no previous smaller height exists:

dp[j] = heights[j] * (j + 1)

because every left boundary from 0 to j is valid.

Step 5: Accumulate the Answer

Add all dp[j] values to the final result.

Each dp[j] counts all valid rectangles ending at column j for the current row.

Why it works

The histogram transformation guarantees that every rectangle of ones ending at the current row corresponds to a contiguous segment in the height array.

The monotonic stack ensures we can efficiently determine the minimum height for every segment without recomputing ranges repeatedly.

The recurrence:

dp[j] = dp[prev] + heights[j] * width

correctly counts all new rectangles introduced by extending intervals to column j.

Since every all-ones submatrix has a unique bottom row and right boundary, every valid rectangle is counted exactly once.

Python Solution

from typing import List

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])

        heights = [0] * cols
        total = 0

        for row in range(rows):
            # Build histogram heights
            for col in range(cols):
                if mat[row][col] == 1:
                    heights[col] += 1
                else:
                    heights[col] = 0

            stack = []
            dp = [0] * cols

            for col in range(cols):
                while stack and heights[stack[-1]] >= heights[col]:
                    stack.pop()

                if stack:
                    prev_smaller = stack[-1]
                    width = col - prev_smaller
                    dp[col] = dp[prev_smaller] + heights[col] * width
                else:
                    dp[col] = heights[col] * (col + 1)

                stack.append(col)
                total += dp[col]

        return total

The implementation begins by maintaining a histogram height array. Each value tracks how many consecutive ones appear vertically up to the current row.

For every row, we update the histogram in O(n) time.

Next, we process the histogram using a monotonic increasing stack. The stack stores indices of columns whose heights are strictly increasing.

When a smaller or equal height appears, taller bars are popped because they can no longer serve as the nearest smaller boundary for future columns.

The dp array stores how many valid submatrices end at each column for the current row.

If a previous smaller height exists, we reuse previously computed results:

dp[col] = dp[prev_smaller] + heights[col] * width

Otherwise, every prefix ending at the current column contributes rectangles.

Finally, all contributions are added into total.

Go Solution

func numSubmat(mat [][]int) int {
	rows := len(mat)
	cols := len(mat[0])

	heights := make([]int, cols)
	total := 0

	for r := 0; r < rows; r++ {
		// Build histogram heights
		for c := 0; c < cols; c++ {
			if mat[r][c] == 1 {
				heights[c]++
			} else {
				heights[c] = 0
			}
		}

		stack := []int{}
		dp := make([]int, cols)

		for c := 0; c < cols; c++ {
			for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[c] {
				stack = stack[:len(stack)-1]
			}

			if len(stack) > 0 {
				prevSmaller := stack[len(stack)-1]
				width := c - prevSmaller
				dp[c] = dp[prevSmaller] + heights[c]*width
			} else {
				dp[c] = heights[c] * (c + 1)
			}

			stack = append(stack, c)
			total += dp[c]
		}
	}

	return total
}

The Go implementation follows the same logic as the Python version.

Slices are used for:

  • heights
  • stack
  • dp

Go does not have Python's dynamic list methods, so stack pops are implemented using slice truncation:

stack = stack[:len(stack)-1]

All calculations safely fit within Go's int type because the maximum number of submatrices for a 150 x 150 matrix is well below integer overflow limits.

Worked Examples

Example 1

Input:

[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

Row 0

Histogram:

[1,0,1]
Column Height Stack dp Total Added
0 1 [0] 1 1
1 0 [1] 0 0
2 1 [1,2] 1 1

Running total:

2

Row 1

Updated histogram:

[2,1,0]
Column Height Stack dp Total Added
0 2 [0] 2 2
1 1 [1] 2 2
2 0 [2] 0 0

Running total:

6

Row 2

Updated histogram:

[3,2,0]
Column Height Stack dp Total Added
0 3 [0] 3 3
1 2 [1] 4 4
2 0 [2] 0 0

Final total:

13

Example 2

Input:

[
  [0,1,1,0],
  [0,1,1,1],
  [1,1,1,0]
]

Row 0

Histogram:

[0,1,1,0]

Contributions:

0 + 1 + 2 + 0 = 3

Row 1

Histogram:

[0,2,2,1]

Contributions:

0 + 2 + 4 + 3 = 9

Running total:

12

Row 2

Histogram:

[1,3,3,0]

Contributions:

1 + 4 + 7 + 0 = 12

Final answer:

24

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell and stack operation is processed at most once per row
Space O(n) Heights, stack, and dp arrays each use linear space

The algorithm processes every matrix cell once while updating histogram heights.

For each row, every column index is pushed and popped from the stack at most one time. Therefore, stack operations are amortized O(n) per row.

This gives total time complexity:

O(m * n)

Additional memory usage comes from:

  • heights
  • dp
  • stack

all of which are proportional to the number of columns.

Test Cases

from typing import List

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])

        heights = [0] * cols
        total = 0

        for row in range(rows):
            for col in range(cols):
                if mat[row][col] == 1:
                    heights[col] += 1
                else:
                    heights[col] = 0

            stack = []
            dp = [0] * cols

            for col in range(cols):
                while stack and heights[stack[-1]] >= heights[col]:
                    stack.pop()

                if stack:
                    prev = stack[-1]
                    dp[col] = dp[prev] + heights[col] * (col - prev)
                else:
                    dp[col] = heights[col] * (col + 1)

                stack.append(col)
                total += dp[col]

        return total

sol = Solution()

assert sol.numSubmat([[1,0,1],[1,1,0],[1,1,0]]) == 13  # provided example 1
assert sol.numSubmat([[0,1,1,0],[0,1,1,1],[1,1,1,0]]) == 24  # provided example 2

assert sol.numSubmat([[1]]) == 1  # single one
assert sol.numSubmat([[0]]) == 0  # single zero

assert sol.numSubmat([[1,1,1]]) == 6  # single row all ones
assert sol.numSubmat([[1],[1],[1]]) == 6  # single column all ones

assert sol.numSubmat([[0,0],[0,0]]) == 0  # all zeros

assert sol.numSubmat([[1,1],[1,1]]) == 9  # fully filled 2x2 matrix

assert sol.numSubmat([[1,0,1,0,1]]) == 3  # separated ones

assert sol.numSubmat([
    [1,1,0],
    [1,1,1],
    [0,1,1]
]) == 19  # mixed structure

assert sol.numSubmat([
    [1,0],
    [0,1]
]) == 2  # diagonal ones only
Test Why
[[1,0,1],[1,1,0],[1,1,0]] Validates the first official example
[[0,1,1,0],[0,1,1,1],[1,1,1,0]] Validates the second official example
[[1]] Smallest valid matrix with one rectangle
[[0]] Smallest matrix with zero valid rectangles
[[1,1,1]] Tests single-row handling
[[1],[1],[1]] Tests single-column handling
[[0,0],[0,0]] Ensures zero-only matrices work
[[1,1],[1,1]] Dense matrix with many overlapping rectangles
[[1,0,1,0,1]] Verifies separated regions are not merged
Mixed 3x3 matrix Tests varying histogram heights
Diagonal ones matrix Ensures disconnected ones are handled correctly

Edge Cases

Matrix Containing Only Zeros

A matrix like:

[
  [0,0],
  [0,0]
]

can expose bugs where the algorithm accidentally counts empty rectangles or fails to reset histogram heights correctly.

The implementation handles this by resetting:

heights[col] = 0

whenever a zero appears. This guarantees no invalid rectangle extends through a zero cell.

Single Row or Single Column

Matrices such as:

[[1,1,1]]

or:

[
 [1],
 [1],
 [1]
]

are important because rectangles reduce to simple contiguous intervals.

Some implementations incorrectly assume two-dimensional behavior and mishandle widths or heights.

This solution works naturally because the histogram method handles width and height independently. The monotonic stack correctly processes even one-dimensional histograms.

Equal Heights in the Histogram

A histogram like:

[2,2,2]

can create duplicate counting problems if the stack condition is wrong.

Using:

while heights[stack[-1]] >= heights[col]:

instead of just > is critical.

This ensures equal heights are merged correctly and prevents counting the same rectangle configurations multiple times.