DSA Tracker

Visualize

Count Square Submatrices with All Ones

dp[i][j] = 1 + min(up, left, diag) when matrix[i][j] = 1

time O(m * n)space O(m * n)

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.

Details

Animated on: matrix = [[1,0,1],[1,1,0],[1,1,0]] — count all square submatrices whose entries are all 1.

Problem:Count Square Submatrices with All OnesMedium

dp[i][j] = 1 + min(up, left, diag) when matrix[i][j] = 1

step 1 / 10

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.

Pseudocode
1FUNCTION countSquares(matrix):
2  FOR EACH cell (i, j):
3    IF matrix[i][j] = 0:
4      dp[i][j] <- 0
5    ELSE IF i = 0 OR j = 0:
6      dp[i][j] <- 1
7    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

Every step in words

Show all 10 steps
  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.
  2. matrix[0][1] = 0, so no square can end here: dp[0][1] = 0.
  3. matrix[0][2] = 1 on the edge (row 0 or column 0), so the biggest square here is just itself: dp[0][2] = 1. Running total = 2.
  4. matrix[1][0] = 1 on the edge (row 0 or column 0), so the biggest square here is just itself: dp[1][0] = 1. Running total = 3.
  5. matrix[1][1] = 1: the square can only grow as far as its WEAKEST neighbour — min(up=0, left=1, diag=1) = 0 — so dp[1][1] = 0 + 1 = 1. Running total = 4.
  6. matrix[1][2] = 0, so no square can end here: dp[1][2] = 0.
  7. matrix[2][0] = 1 on the edge (row 0 or column 0), so the biggest square here is just itself: dp[2][0] = 1. Running total = 5.
  8. matrix[2][1] = 1: the square can only grow as far as its WEAKEST neighbour — min(up=1, left=1, diag=1) = 1 — so dp[2][1] = 1 + 1 = 2. Running total = 7.
  9. matrix[2][2] = 0, so no square can end here: dp[2][2] = 0.
  10. Every dp[i][j] IS the count of squares of every size anchored at (i, j) — a 2x2 square contains a 1x1 one, a 3x3 contains a 2x2 and a 1x1. Summing all of dp gives the total: 7.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Square Submatrices with All Ones in the editorAll Dynamic Programming problemsBack to roadmap