Problem Breakdown
We are given a binary matrix of dimensions . 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 .
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=0orn=0. - All Zeros: If the matrix contains no ones, the result is 0.
- Single Row/Column: Squares of size are impossible; only squares of side length 1 count (where value is 1).
- Overflow: The maximum possible answer for a matrix of all ones involves summing triangular numbers. For an grid, the max count is roughly . With , this fits comfortably within standard integer limits (approx ).
Intuition
A naive approach would be to iterate over every possible top-left corner and for each one, check all square sizes starting there. This involves checking submatrices repeatedly or iterating side lengths . For a fixed size , we verify if the border is valid.
- Brute Force Complexity: Iterating through all cells as corners () and then expanding squares up to takes roughly cubic time per cell in worst case checks or quadratic overall depending on implementation: . This is too slow for 300x300.
Key Insight:
Consider a specific cell 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 square ending at (i,j), we need sized squares above, left, and diagonally. The bottleneck is the smallest of these neighbors.
Counting Logic: If dp[i][j] equals , it means there are exactly 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
- Initialize a
dpmatrix of size . 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. - Iterate through each cell
(i, j)from top-left to bottom-right (order doesn’t strictly matter as long as dependencies are met). - For boundary cells (
i=0orj=0) where the value is 1, they can only form squares of size 1 ending there. Sodp[i][j] = matrix[i][j]. - 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. - Accumulate every computed
dp[i][j]into a running total counter. - Return the accumulated sum.
Complexity Analysis
- Time Complexity: . We visit each cell exactly once performing constant time operations (min of 3 values). With max dimensions 300, this is roughly operations, which is negligible.
- Space Complexity: for the DP table. This can be optimized to 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 ). - 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
dpexplicitly rather than modifyingmatrix, the solution does not alter the caller’s data structure, preventing bugs if the matrix is reused elsewhere.