Count Square Submatrices with All Ones

Count Square Submatrices with All Ones

What is this problem about?

The "Count Square Submatrices with All Ones interview question" is a matrix optimization problem. You are given an $m imes n$ binary matrix (containing only 0s and 1s). Your task is to count how many square submatrices have all their elements equal to 1. Squares can be of any size from $1 imes 1$ up to the smaller dimension of the matrix.

Why is this asked in interviews?

Meta, Microsoft, and Google frequently use the "Count Square Submatrices coding problem" to test a candidate's mastery of Dynamic Programming. It is a great way to evaluate if a candidate can build a solution where each cell's value depends on its neighbors. It also tests the ability to optimize for both time ($O(M imes N)$) and space.

Algorithmic pattern used

This problem is solved using Dynamic Programming.

1. State Definition: Let dp[i][j] be the side length of the largest square submatrix whose bottom-right corner is at $(i, j)$.
2. The "Min" Insight: If matrix[i][j] is 1, the largest square ending there is limited by the squares ending above it, to its left, and diagonally above-left. Specifically: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
3. Summation: The value dp[i][j] also represents the total number of squares of all possible sizes that have $(i, j)$ as their bottom-right corner. Therefore, the total count is simply the sum of all values in the dp table.

Example explanation

Matrix:

0 1 1 1
1 1 1 1
0 1 1 1

• For cell (1, 1), neighbors (0,1), (1,0), (0,0) are 1, 1, 0. min(1, 1, 0) + 1 = 1. One square (size 1) ends here.
• For cell (1, 2), neighbors (0,2), (1,1), (0,1) are 1, 1, 1. min(1, 1, 1) + 1 = 2. Two squares (size 1 and size 2) end here. Summing these values across the grid gives the total count.

Common mistakes candidates make

• Checking Sizes Individually: Trying to check every possible square of every size ($O(N^4)$ or $O(N^3)$), which will time out.
• Edge Cases: Failing to handle the first row and first column correctly (where $i-1$ or $j-1$ are out of bounds).
• Misinterpreting dp[i][j]: Not realizing that the value at a cell directly corresponds to the number of squares ending there.

Interview preparation tip

Master the "Matrix DP interview pattern." Many grid problems (like "Largest Square" or "Maximal Rectangle") use similar neighbor-dependency logic. If a problem involves finding or counting shapes in a grid, DP is often the most efficient tool.