Domain 2MediumMEDIUM

Count Square Submatrices with All Ones

LeetCode problem 1277: Count Square Submatrices with All Ones (medium).

Domain: medium•Updated: 2026-09-13
#Array#Dynamic Programming

Problem Breakdown

We are given a binary matrix of dimensions m×nm \times n. The goal is to calculate the total number of square submatrices that consist entirely of ones (1s).

Inputs: A 2D list matrix containing only integers 0 or 1. Dimensions up to 300×300300 \times 300. Outputs: An integer representing the count of valid all-ones squares.

Implicit Constraints & Edge Cases:

  • Empty Input: The constraints state dimensions are at least 1, so we don’t strictly need empty checks for logic correctness, but robust code handles m=0 or n=0.
  • All Zeros: If the matrix contains no ones, the result is 0.
  • Single Row/Column: Squares of size >1>1 are impossible; only squares of side length 1 count (where value is 1).
  • Overflow: The maximum possible answer for a 300×300300 \times 300 matrix of all ones involves summing triangular numbers. For an N×NN \times N grid, the max count is roughly N44\frac{N^4}{4}. With N=300N=300, this fits comfortably within standard integer limits (approx 2⋅109<263−12 \cdot 10^9 < 2^{63}-1).

Intuition

A naive approach would be to iterate over every possible top-left corner (r,c)(r, c) and for each one, check all square sizes starting there. This involves checking submatrices repeatedly or iterating side lengths kk. For a fixed size kk, we verify if the border is valid.

  • Brute Force Complexity: Iterating through all cells as corners (O(m⋅n)O(m \cdot n)) and then expanding squares up to min⁡(m,n)\min(m, n) takes roughly cubic time per cell in worst case checks or quadratic overall depending on implementation: O(m⋅n⋅(min⁡(m,n))2)O(m \cdot n \cdot (\min(m,n))^2). This is too slow for 300x300.

Key Insight: Consider a specific cell (i,j)(i, j) that contains a 1. If this cell acts as the bottom-right corner of an all-ones square, what determines its size? It depends on how many consecutive ones extend upwards and to the left from it. Specifically, if we know the largest square ending at (i-1, j) (above) and (i, j-1) (left), plus the diagonal neighbor (i-1, j-1), we can determine the max size of a new square ending at (i,j).

If matrix[i][j] == 0, no all-ones square ends here. If matrix[i][j] == 1, then: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

Why? Because to form a k×kk \times k square ending at (i,j), we need (k−1)(k-1) sized squares above, left, and diagonally. The bottleneck is the smallest of these neighbors. Counting Logic: If dp[i][j] equals KK, it means there are exactly KK valid all-ones squares whose bottom-right corner is (i,j) (sizes 1 through K). Therefore, we simply sum every value in our DP table to get the total count of squares.

Approach

  1. Initialize a dp matrix of size m×nm \times n. We can reuse this space or modify input if allowed; for clarity and safety against side effects, I’ll allocate new memory here but note that we could optimize it later.
  2. Iterate through each cell (i, j) from top-left to bottom-right (order doesn’t strictly matter as long as dependencies are met).
  3. For boundary cells (i=0 or j=0) where the value is 1, they can only form squares of size 1 ending there. So dp[i][j] = matrix[i][j].
  4. For internal cells with a 1, apply the recurrence: take minimum of top, left, and diagonal neighbors in DP table, add 1. If neighbor is out of bounds or value was 0 (handled by initialization), treat as limiting factor.
  5. Accumulate every computed dp[i][j] into a running total counter.
  6. Return the accumulated sum.

Complexity Analysis

  • Time Complexity: O(m⋅n)O(m \cdot n). We visit each cell exactly once performing constant time operations (min of 3 values). With max dimensions 300, this is roughly 90,00090,000 operations, which is negligible.
  • Space Complexity: O(m⋅n)O(m \cdot n) for the DP table. This can be optimized to O(1)O(1) auxiliary space by modifying the input matrix in-place (since we don’t need original values after processing), but allocating a separate array ensures immutability of inputs, which is preferred in production code unless memory constraints dictate otherwise.

Solution

from typing import List

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        
        # Initialize DP table. 
        # We use a separate array to avoid modifying input data structure (side effects).
        dp = [[0] * n for _ in range(m)]
        
        total_count = 0
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    # If we are not on the first row or column, check neighbors.
                    # Otherwise (first row/col), max square size ending here is just 1 
                    # because there's no space above/left to extend a larger square.
                    
                    if i > 0 and j > 0:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    else:
                        # Boundary case (first row or first col)
                        dp[i][j] = matrix[i][j] 
                    
                    total_count += dp[i][j]
                else:
                    # If current cell is 0, no square can end here.
                    dp[i][j] = 0
                    
        return total_count

Edge Cases Handled

  • Empty Matrix: The check if not matrix or not matrix[0]: handles cases where input dimensions might be zero (though constraints say ≥1\ge 1).
  • All Zeros: If no cells are 1, the loop never adds to total_count, returning 0 correctly.
  • Single Row/Column: The boundary logic (i > 0 and j > 0) ensures that for first row/column indices, we only count size-1 squares (value of cell itself), which is correct as larger squares cannot exist in a single dimension.
  • Input Mutation Safety: By creating dp explicitly rather than modifying matrix, the solution does not alter the caller’s data structure, preventing bugs if the matrix is reused elsewhere.