LeetCode 1277 - Count Square Submatrices with All Ones

The problem gives us a binary matrix of size m x n, where every cell contains either 0 or 1. We must count how many squa

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 1277

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

Solution

Problem Understanding

The problem gives us a binary matrix of size m x n, where every cell contains either 0 or 1. We must count how many square submatrices contain only ones.

A square submatrix is any contiguous square region inside the matrix. The square can have side length 1, 2, 3, and so on, as long as it stays within the matrix boundaries.

For example, a single cell containing 1 counts as a valid square of size 1 x 1. A 2 x 2 region counts only if all four cells are 1. Similarly, a 3 x 3 region counts only if every cell inside it is 1.

The output is the total number of valid square submatrices of every possible size.

The constraints are important:

  • 1 <= m, n <= 300
  • Each cell is either 0 or 1

A 300 x 300 matrix contains up to 90,000 cells. This means an algorithm with cubic or quartic complexity could become too slow. We need something close to O(m * n).

Several edge cases are important:

  • A matrix filled entirely with zeros should return 0
  • A matrix filled entirely with ones produces many overlapping squares
  • Single row or single column matrices can only contain 1 x 1 squares
  • Sparse matrices with isolated ones should not incorrectly form larger squares
  • Large connected regions of ones must correctly count all possible square sizes

The key challenge is efficiently determining whether larger squares are valid without repeatedly scanning every cell inside them.

Approaches

Brute Force Approach

A straightforward solution is to try every possible square.

For every cell in the matrix, we treat it as the top left corner of a potential square. Then we try every possible side length that fits inside the matrix. For each candidate square, we scan all cells inside that square to verify whether every value is 1.

If all cells are ones, we increment the answer.

This approach is correct because it explicitly checks every possible square submatrix. However, it is inefficient because verifying each square requires scanning its contents repeatedly.

Suppose the matrix dimensions are m x n. There are approximately O(m * n * min(m, n)) possible squares, and validating each one may take O(k^2) time for side length k. In the worst case, the complexity becomes roughly O(m * n * min(m, n)^3), which is far too slow for matrices up to 300 x 300.

Dynamic Programming Insight

The key observation is that if we already know the largest square ending at neighboring cells, we can determine the largest square ending at the current cell efficiently.

Define:

dp[i][j] = size of the largest square whose bottom right corner is at (i, j).

If matrix[i][j] == 0, then no square can end there, so:

dp[i][j] = 0

If matrix[i][j] == 1, then the square size depends on three neighboring cells:

  • top: dp[i-1][j]
  • left: dp[i][j-1]
  • top-left diagonal: dp[i-1][j-1]

The current square can only expand if all three neighboring regions can support it. Therefore:

$dp[i][j]=1+\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])$

This works because the smallest neighboring square limits how large the current square can become.

Every dp[i][j] value directly tells us how many valid squares end at that cell:

  • If dp[i][j] = 1, there is one square
  • If dp[i][j] = 2, there are two squares
  • If dp[i][j] = 3, there are three squares

So we simply sum all DP values.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * min(m, n)^3) O(1) Checks every possible square explicitly
Optimal Dynamic Programming O(m * n) O(m * n) Reuses previous computations to build larger squares efficiently

Algorithm Walkthrough

  1. Create a DP table with the same dimensions as the input matrix.

Each dp[i][j] stores the size of the largest square ending at cell (i, j). 2. Initialize a variable total_squares = 0.

This variable accumulates the total number of valid square submatrices. 3. Traverse the matrix row by row and column by column.

At each cell, determine whether a square can end there. 4. Handle cells containing 0.

If matrix[i][j] == 0, then no square can end at this position. Set:

dp[i][j] = 0
  1. Handle boundary cells separately.

If the cell contains 1 and lies in the first row or first column, the largest possible square has side length 1.

dp[i][j] = 1
  1. Process interior cells.

For cells not on the boundary, if matrix[i][j] == 1, compute:

$dp[i][j]=1+\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])$

The smallest neighboring square determines whether we can extend to a larger square. 7. Add dp[i][j] to the answer.

If dp[i][j] = k, then there are exactly k valid squares ending at (i, j). 8. Continue until all cells are processed. 9. Return total_squares.

Why it works

The DP state maintains an important invariant:

dp[i][j] always equals the side length of the largest all-ones square ending at (i, j).

A square of side length k can only exist if:

  • the top neighbor supports at least k-1
  • the left neighbor supports at least k-1
  • the diagonal neighbor supports at least k-1

If any one of these is smaller, the square cannot expand further. Taking the minimum guarantees correctness.

Because every valid square has a unique bottom right corner, summing all DP values counts every square exactly once.

Python Solution

from typing import List

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

        dp = [[0] * cols for _ in range(rows)]
        total_squares = 0

        for row in range(rows):
            for col in range(cols):

                if matrix[row][col] == 0:
                    dp[row][col] = 0

                elif row == 0 or col == 0:
                    dp[row][col] = 1

                else:
                    dp[row][col] = 1 + min(
                        dp[row - 1][col],
                        dp[row][col - 1],
                        dp[row - 1][col - 1]
                    )

                total_squares += dp[row][col]

        return total_squares

The implementation begins by determining the matrix dimensions. A DP table of equal size is allocated, where each entry stores the largest square ending at that location.

The nested loops iterate through every cell exactly once.

If the current cell contains 0, no square can terminate there, so the DP value remains 0.

If the current cell lies on the top row or leftmost column and contains 1, the largest possible square has size 1.

For all other cells containing 1, the solution computes the minimum among the top, left, and diagonal neighbors, then adds 1. This efficiently determines the largest extendable square.

After computing each DP value, it is immediately added to the running total because every DP value represents the number of valid squares ending at that cell.

Finally, the function returns the accumulated count.

Go Solution

func countSquares(matrix [][]int) int {
    rows := len(matrix)
    cols := len(matrix[0])

    dp := make([][]int, rows)

    for i := 0; i < rows; i++ {
        dp[i] = make([]int, cols)
    }

    totalSquares := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {

            if matrix[row][col] == 0 {
                dp[row][col] = 0

            } else if row == 0 || col == 0 {
                dp[row][col] = 1

            } else {
                dp[row][col] = 1 + min(
                    dp[row-1][col],
                    min(
                        dp[row][col-1],
                        dp[row-1][col-1],
                    ),
                )
            }

            totalSquares += dp[row][col]
        }
    }

    return totalSquares
}

func min(a int, b int) int {
    if a < b {
        return a
    }

    return b
}

The Go implementation follows the same DP logic as the Python version. Since Go does not provide a built in integer min function for this use case, a helper function is defined manually.

The DP table is created using slices of slices. Each row is initialized independently.

Go integers are sufficient for this problem because the maximum possible answer is well within 32 bit integer range.

Worked Examples

Example 1

Input:

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

We build the DP table step by step.

Initial DP table:

Row Values
0 [0,0,0,0]
1 [0,0,0,0]
2 [0,0,0,0]

Processing row 0:

Cell DP Value Reason
(0,0) 0 matrix value is 0
(0,1) 1 boundary cell with 1
(0,2) 1 boundary cell with 1
(0,3) 1 boundary cell with 1

DP now:

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

Running total: 3

Processing row 1:

Cell Computation DP Value
(1,0) boundary cell 1
(1,1) 1 + min(1,1,0) 1
(1,2) 1 + min(1,1,1) 2
(1,3) 1 + min(1,2,1) 2

DP now:

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

Running total: 9

Processing row 2:

Cell Computation DP Value
(2,0) matrix value is 0 0
(2,1) 1 + min(1,0,1) 1
(2,2) 1 + min(2,1,1) 2
(2,3) 1 + min(2,2,2) 3

Final DP:

[
  [0,1,1,1],
  [1,1,2,2],
  [0,1,2,3]
]

Total:

0+1+1+1+
1+1+2+2+
0+1+2+3 = 15

Example 2

Input:

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

DP construction:

Position DP Value
(0,0) 1
(0,1) 0
(0,2) 1
(1,0) 1
(1,1) 1
(1,2) 0
(2,0) 1
(2,1) 2
(2,2) 0

Final DP table:

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

Total:

1+0+1+
1+1+0+
1+2+0 = 7

The 2 at (2,1) indicates:

  • one 1 x 1 square
  • one 2 x 2 square

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is processed exactly once
Space O(m * n) DP table stores one value per cell

The algorithm performs constant work for every matrix cell. No nested rescanning occurs, which keeps the runtime linear in the number of cells.

The DP table requires additional storage proportional to the matrix size. Although space optimization to O(n) is possible, the full table improves readability and clarity.

Test Cases

from typing import List

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

        dp = [[0] * cols for _ in range(rows)]
        total_squares = 0

        for row in range(rows):
            for col in range(cols):

                if matrix[row][col] == 0:
                    dp[row][col] = 0

                elif row == 0 or col == 0:
                    dp[row][col] = 1

                else:
                    dp[row][col] = 1 + min(
                        dp[row - 1][col],
                        dp[row][col - 1],
                        dp[row - 1][col - 1]
                    )

                total_squares += dp[row][col]

        return total_squares

solution = Solution()

assert solution.countSquares([
    [0,1,1,1],
    [1,1,1,1],
    [0,1,1,1]
]) == 15  # provided example 1

assert solution.countSquares([
    [1,0,1],
    [1,1,0],
    [1,1,0]
]) == 7  # provided example 2

assert solution.countSquares([
    [0]
]) == 0  # single zero cell

assert solution.countSquares([
    [1]
]) == 1  # single one cell

assert solution.countSquares([
    [1,1,1]
]) == 3  # single row, only 1x1 squares

assert solution.countSquares([
    [1],
    [1],
    [1]
]) == 3  # single column, only 1x1 squares

assert solution.countSquares([
    [1,1],
    [1,1]
]) == 5  # four 1x1 squares and one 2x2 square

assert solution.countSquares([
    [0,0],
    [0,0]
]) == 0  # all zeros

assert solution.countSquares([
    [1,1,1],
    [1,1,1],
    [1,1,1]
]) == 14  # all possible square sizes

assert solution.countSquares([
    [1,0,1],
    [0,1,0],
    [1,0,1]
]) == 5  # isolated ones, no larger squares

assert solution.countSquares([
    [1,1,0],
    [1,1,1],
    [0,1,1]
]) == 9  # mixed structure with overlapping squares
Test Why
Example 1 Validates multiple square sizes
Example 2 Validates irregular square formation
Single zero Smallest invalid input
Single one Smallest valid input
Single row Ensures no larger squares form horizontally
Single column Ensures no larger squares form vertically
Full 2x2 ones Validates one larger square
All zeros Confirms correct zero handling
Full 3x3 ones Tests maximum overlapping squares
Isolated ones Prevents false square expansion
Mixed structure Validates dynamic programming transitions

Edge Cases

One important edge case is a matrix containing only zeros. A naive implementation might accidentally count invalid squares if it does not carefully verify every cell. In this implementation, any cell containing 0 immediately produces dp[i][j] = 0, ensuring no square can end there.

Another important case is a single row or single column matrix. Larger squares require both height and width, so only 1 x 1 squares are possible. The implementation handles this naturally because boundary cells are assigned value 1 when they contain ones, and no larger expansion occurs.

A third critical edge case involves isolated ones separated by zeros. For example:

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

A buggy implementation might incorrectly combine nearby ones into larger squares. The DP transition prevents this because expanding a square requires all three neighboring DP states to support the expansion. A single zero blocks growth immediately.

A fourth subtle case occurs with large fully connected regions of ones. In these cases, the number of overlapping squares grows rapidly. The DP approach handles this efficiently because each cell computation reuses previously computed information rather than rescanning entire submatrices repeatedly.