Count Square Submatrices with All Ones

Medium Dynamic Programming Squares Original on LeetCode

Reported atAmerican Express

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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(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.

  1. Grow each square layer by layer while it stays all 1s; count each size.
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.

  1. For i, j >= 1 with matrix[i][j] == 1: matrix[i][j] = 1 + min(three neighbours).
  2. Sum every cell.
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.