Count Square Submatrices with All Ones

Medium Dynamic Programming Squares Original on LeetCode

Count Square Submatrices with All Ones is a medium dynamic programming problem solved with the squares pattern. The best approach, optimal (same dp as maximal square, then sum), runs in O(m · n) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

Count all square submatrices consisting entirely of 1s, of every size.

Examples

Example 1

Input: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output: 15
Why: 10 squares of side 1, 4 of side 2, 1 of side 3.

Example 2

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

Constraints

1 <= m, n <= 300; values 0 or 1.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(m · n · min(m, n)²)`	`O(1)`
Optimal (same DP as Maximal Square, then sum)	`O(m · n)`	`O(1)`

1Brute force

TimeO(m · n · min(m, n)²)

SpaceO(1)

For every top-left corner and every size, check whether the square is all 1s.

Grow each square layer by layer while it stays all 1s; count each size.

Java

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length, count = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int size = 0;
                grow:
                while (i + size < m && j + size < n) {
                    for (int k = 0; k <= size; k++)
                        if (matrix[i + size][j + k] != 1 || matrix[i + k][j + size] != 1) break grow;
                    size++;
                    count++;
                }
            }
        return count;
    }
}

2Optimal (same DP as Maximal Square, then sum)

TimeO(m · n)

SpaceO(1)Updates the input in place.

dp[i][j] = 1 + min(top, left, top-left) for each 1. Each dp value counts the squares whose bottom-right corner is that cell, so the answer is the sum of the table. It can be computed in place.

For i, j >= 1 with matrix[i][j] == 1: matrix[i][j] = 1 + min(three neighbours).
Sum every cell.

Java

class Solution {
    public int countSquares(int[][] matrix) {
        int total = 0;
        for (int i = 0; i < matrix.length; i++)
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1 && i > 0 && j > 0)
                    matrix[i][j] = 1 + Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1]));
                total += matrix[i][j];
            }
        return total;
    }
}

Edge cases to test

All zeros

Hints

Hint 1

If the largest square ending at (i, j) has side s, then exactly s squares end there (sides 1..s). Sum the DP table.

FAQ

What is the best time complexity for Count Square Submatrices with All Ones?

Optimal (same DP as Maximal Square, then sum) runs in O(m · n) time and O(1) extra space.

Which pattern does Count Square Submatrices with All Ones use?

It is a dynamic programming problem that uses the squares pattern. Other problems with the same pattern: Maximal Square, Largest 1-Bordered Square.

Is there a brute force solution for Count Square Submatrices with All Ones?

Yes. Brute force takes O(m · n · min(m, n)²) time and O(1) space. For every top-left corner and every size, check whether the square is all 1s.

Which edge cases should I test for Count Square Submatrices with All Ones?

All zeros.