We are given a 2D binary matrix of integers (0s and 1s) and we need to count every square submatrix that consists entirely of 1s. A 1x1 cell with value 1 counts as a square. A 2x2 block of all 1s counts as one more square. A 3x3 block of all 1s adds yet another, and so on.

We are counting squares of every size, not finding the largest one. If a cell can be the bottom-right corner of a 3x3 all-ones square, it is also the bottom-right corner of a 2x2 and a 1x1 all-ones square. So a cell whose largest square has side length k contributes exactly k squares to the total count. The DP approach builds on this observation.

Key Constraints:

Intuition

For every possible top-left corner (i, j) and every possible side length k, check whether all k*k cells inside that square are 1. If they are, count it. This implements the definition directly.

For each cell where matrix[i][j] == 1, we try side lengths 1, 2, 3, ... as long as the square fits within the matrix, scanning every cell inside each candidate square. Once a side length fails, we can stop expanding from that corner: any larger square from the same corner contains the failing square, so it contains the same 0.

Algorithm

Example Walkthrough

Input:

Each cell (i, j) is the top-left corner of the candidate squares, which grow down and to the right.

Total = 3 + 2 + 1 + 1 + 2 + 2 + 1 + 1 + 1 + 1 = 15, which is the returned answer.

Code

Every square is verified from scratch even though it overlaps heavily with squares already checked. Dynamic programming removes the repeated scanning: the largest all-ones square ending at a cell can be computed in O(1) from three already-computed neighbors.

Intuition

Define dp[i][j] as the side length of the largest all-ones square whose bottom-right corner is at position (i, j). If matrix[i][j] is 0, then dp[i][j] = 0 since no all-ones square can end at a 0 cell.

For a cell where matrix[i][j] == 1, being the bottom-right corner of a k x k square requires the cell above, the cell to the left, and the cell diagonally above-left to each be the bottom-right corner of an all-ones square of side at least k-1. The weakest neighbor limits how far the square extends, giving the recurrence:

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

The same table answers the counting question. If dp[i][j] = 3, that cell is the bottom-right corner of a 3x3, a 2x2, and a 1x1 all-ones square, so it contributes exactly 3 squares. Summing all dp values counts every square exactly once, because each square has exactly one bottom-right corner.

Algorithm

Example Walkthrough

The trace below fills the dp table for matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]] (Example 1), row by row.

Code

The time is already optimal, but the space matches the input size. Since the recurrence only depends on the current and previous row, we can compress the dp table to a single row.

Intuition

Computing dp[i][j] reads three values: dp[i-1][j] (same column, previous row), dp[i][j-1] (previous column, current row), and dp[i-1][j-1] (diagonal, previous row). Only the current row and the previous row are needed at any time, and both fit in a single 1D array processed row by row.

The complication is the diagonal value. As we update dp[j] left to right, dp[j] still holds the value from the previous row (that is dp[i-1][j]), and dp[j-1] was already updated for the current row (that is dp[i][j-1]). But we also need dp[i-1][j-1], the old value of dp[j-1] before we overwrote it. So before each update we save the cell's outgoing value in a variable prev, where the next column can read it as the diagonal.

Algorithm

Example Walkthrough

This trace uses matrix = [[1,0,1],[1,1,0],[1,1,0]] (Example 2, answer 7). Only the 1D dp array is shown; it is overwritten in place as each row is processed.

Code