Count Square Submatrices with All Ones

Medium20–25 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonMicrosoft

Given a binary matrix, count how many square submatrices — of any size, 1×1 and up — are made entirely of 1s. Trying every square directly, with a prefix-sum table to check each one in O(1), already works. The faster way notices something sharper: define dp[r][c] as the side length of the biggest all-1s square that has its bottom-right corner exactly at (r, c). That value can only grow past 1 if a square one size smaller already ends at the cell above, the cell to the left, *and* the cell diagonally above-left — so dp[r][c] is the smallest of those three neighbors, plus one. The neat payoff: dp[r][c] doesn't just say how big the largest square there is, it also equals how many squares of every size up to that end there — a size-3 square ending somewhere means a size-2 and a size-1 do too, at the very same corner. Summing dp[r][c] across the whole grid is the answer.

Test Case 1:

Input:matrix = [[1,0,1],[1,1,0],[1,1,1]]

Output:8

Explanation:6 squares of size 1×1, plus a 2×2 square with its bottom-right corner at row 2, column 1 — that one 2×2 accounts for 2 more toward the total (1×1 squares are already counted, so it adds just the size-2 count).

Test Case 2:

Input:matrix = [[0,1,1],[1,1,1],[0,1,1]]

Output:9

Explanation:7 size-1×1 squares and 2 size-2×2 squares (one in the top-right area, one in the bottom-right).

Test Case 3:

Input:matrix = [[0,0],[0,0]]

Output:0

Explanation:No 1s at all, so no square — not even a 1×1 one.

Constraints

◆1 ≤ rows, cols ≤ 200
◆every entry of matrix is either 0 or 1

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Prefix Sums Over Every Candidate Square

Brute

For every possible top-left corner, try every possible square size that still fits within the grid from there, and use a 2D prefix-sum table to check in O(1) whether that size×size region is entirely 1s. There are O(R·C) starting corners and up to O(min(R,C)) sizes to try from each one.

TimeO(R · C · min(R, C))

SpaceO(R · C)

Java

Try it out

class Solution {
    public int countSquares(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        int[][] prefix = new int[rows + 1][cols + 1];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                prefix[r + 1][c + 1] = matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];
            }
        }
        int count = 0;
        for (int top = 0; top < rows; top++) {
            for (int left = 0; left < cols; left++) {
                int maxSize = Math.min(rows - top, cols - left);
                for (int size = 1; size <= maxSize; size++) {
                    int bottom = top + size - 1;
                    int right = left + size - 1;
                    int sum = prefix[bottom + 1][right + 1] - prefix[top][right + 1] - prefix[bottom + 1][left] + prefix[top][left];
                    if (sum == size * size) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

Optimal — DP: Largest Square Ending at Each Cell

Optimal

Let dp[r][c] be the side length of the largest all-1s square whose bottom-right corner is exactly cell (r, c). If matrix[r][c] is 0, no square can end there — dp[r][c] = 0. Otherwise a square of side k can only end here if squares of side k-1 already end at the cell above, the cell to the left, and the cell diagonally above-left — so dp[r][c] is one more than the smallest of those three neighbors. The key trick: dp[r][c] doesn't just tell you the biggest square ending there — it tells you exactly how many squares (of every size from 1 up to dp[r][c]) end there, since every smaller size is automatically achievable too. Summing dp[r][c] over the whole grid is the total count.

TimeO(R · C)