Count Square Submatrices with All Ones
Problem
m × n grid made only of 0s and
1s. Count how many square sub-grids (of any size, at any position)
contain nothing but 1s. Squares of different sizes or positions are counted
separately.[[0,1,1,1],[1,1,1,1],[0,1,1,1]]Output15[[1,0,1],[1,1,0],[1,1,0]]Output71 ≤ m, n ≤ 300 · matrix[i][j] ∈ {0, 1}
Try it yourself
class Solution {
public int countSquares(int[][] matrix) {
}
}
dp[i][j] = side of the largest all-ones square whose
bottom-right corner is (i,j). It is also the number of squares
ending there (sides 1..dp), so the answer is simply the sum of all dp values.Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.
Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.
Open the Grid DP guide →Approaches
Brute ForceGrow Every Square & Re-check
O(m·n·k3)Space O(1)For every top-left cell, try sides 1, 2, … up to
k = min(m, n) and scan the whole square for a 0. Once a
side fails, every larger square from that corner contains it too, so stop early.
Re-scanning size2 cells per side gives the cubic factor.
public int countSquares(int[][] matrix) { int m = matrix.length, n = matrix[0].length, count = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) for (int size = 1; size <= Math.min(m - i, n - j); size++) { if (!allOnes(matrix, i, j, size)) break; // bigger ones fail too count++; } return count; } private boolean allOnes(int[][] a, int r, int c, int size) { for (int i = r; i < r + size; i++) for (int j = c; j < c + size; j++) if (a[i][j] != 1) return false; return true; }
Simple and obviously correct, but repeats almost all of its work.
Better2-D DP (Bottom-Right Corner)
O(m·n)Space O(m·n)A square of side s ends at (i,j) only if squares of
side s-1 end at its top, left and top-left neighbours. So for a
1 cell, dp[i][j] = 1 + min(top, left, diag); for a
0 it is 0. Add every dp value to the count.
public int countSquares(int[][] matrix) { int m = matrix.length, n = matrix[0].length, count = 0; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) dp[i][j] = (i == 0 || j == 0) ? 1 : 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])); count += dp[i][j]; } return count; }
Linear in the grid size; the full table is only needed for the previous row.
Optimal1-D Rolling Row
O(m·n)Space O(n)Keep one row dp. Before overwriting dp[j] it still
holds the cell above; dp[j-1] is already the cell to the
left; the old dp[j-1] (saved in diag) is the
top-left. Using size n+1 removes the edge checks.
public int countSquares(int[][] matrix) { int m = matrix.length, n = matrix[0].length, count = 0; int[] dp = new int[n + 1]; // dp[j + 1] <-> column j for (int i = 0; i < m; i++) { int diag = 0; for (int j = 1; j <= n; j++) { int above = dp[j]; dp[j] = matrix[i][j - 1] == 1 ? 1 + Math.min(diag, Math.min(above, dp[j - 1])) : 0; diag = above; count += dp[j]; } } return count; }
Dry run[[0,1,1,1],[1,1,1,1],[0,1,1,1]] (dp[1..4])
- row 00111count = 3
- row 11122+6 → count = 9
- row 20123+6 → 15 ✔
Same recurrence, same speed, memory cut to one row.
dp straight into
matrix for O(1) extra space.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Grow Every Square & Re-check | O(m·n·k3) | O(1) |
| Better | 2-D DP (Bottom-Right Corner) | O(m·n) | O(m·n) |
| Optimal | 1-D Rolling Row | O(m·n) | O(n) |
- Counting only the largest square per cell — a side-3 square also contains sides 1 and 2.
- Taking
minof only top and left — the diagonal neighbour matters too. - Rolling row: reading the updated
dp[j]as “above” — save it first.
- Name the state precisely: largest square ending at (i,j) as bottom-right.
- Explain why
dp[i][j]doubles as a count of squares ending there. - Link it to Maximal Square (221): same table, take max instead of sum.