DSA problem
Count Square Submatrices with All Ones
Given an m x n binary matrix, return the total number of square submatrices that contain only 1s. Submatrices of different sizes and different positions all count separately.
This problem is the counting twin of "Maximal Square." The same recurrence drives both: let dp[i][j] be the side length of the largest all-ones square whose bottom-right corner is (i, j). The crucial observation is that dp[i][j] is not just the size of the biggest square ending here — it is exactly the number of all-ones squares that end here. Why? Because if the largest such square has side s, then squares of side 1, 2, ..., s all also end at (i, j) (each is the bottom-right k x k block of the largest). Each contributes exactly one to the global count.
So the algorithm reuses the Maximal-Square DP: dp[i][j] = 0 if matrix[i][j] == 0, else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]). The answer is simply the sum of all dp[i][j]. This is a textbook "DP value is also the count of something" identity, and it avoids any separate enumeration of square sizes.
The optimal space-optimized version uses a single 1-D dp array of length n and a prev scalar for the diagonal predecessor, exactly as in Maximal Square — except we accumulate a running total instead of a running max. Total complexity: O(m * n) time and O(n) space.
Examples
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]15matrix = [[1,0,1],[1,1,0],[1,1,0]]7matrix = [[0,0],[0,0]]0Constraints
- 1 <= m, n <= 300
- Each cell of `matrix` is either 0 or 1.
- The result counts squares of every possible size from 1x1 up to min(m, n) x min(m, n).
- Different positions of the same-size square count separately.
- The answer fits in a 32-bit signed integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.