Pattern visualizer
Count Square Submatrices with All Ones
Let dp[i][j] be the side length of the largest all-ones square whose bottom-right corner sits at (i, j). A square of side k ending here needs a square of side at least k-1 ending at all three neighbours above, to the left, and diagonally above-left — so dp[i][j] = 1 + the SMALLEST of those three, the weakest link that limits how far the square can grow. The trick that makes dp[i][j] answer the count directly: a square of side k anchored here contains a square of side k-1, k-2, ... 1 also anchored here, so dp[i][j] IS the number of squares ending at that cell, of every size. Summing dp over the whole grid counts every square in the matrix exactly once. Animated on: matrix = [[1,0,1],[1,1,0],[1,1,0]] — count all square submatrices whose entries are all 1..
dp[i][j] = 1 + min(up, left, diag) when matrix[i][j] = 1
matrix[0][0] = 1 on the edge (row 0 or column 0), so the biggest square here is just itself: dp[0][0] = 1. Running total = 1.
1FUNCTION countSquares(matrix):2 FOR EACH cell (i, j):3 IF matrix[i][j] = 0:4 dp[i][j] <- 05 ELSE IF i = 0 OR j = 0:6 dp[i][j] <- 17 ELSE:8 dp[i][j] <- 1 + MIN(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])9 RETURN SUM of all dp[i][j]
← / → step · space play · Home restart