Count Square Submatrices with All Ones

Medium
291.

Count Square Submatrices with All Ones

Count Square Submatrices with All Ones is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.

Given an m × n matrix of ones and zeros, return how many square submatrices consist entirely of ones. Squares of every size count, including 1 × 1.

Example 1

Input
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output
15
Explanation
There are 10 squares of side 1, 4 of side 2 and 1 of side 3.

Example 2

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

Example 3

Input
matrix = [[1]]
Output
1

Constraints

  • 1 <= matrix.length, matrix[i].length <= 8
  • matrix[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var countSquares = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Square Submatrices with All Ones — Problem & Solution

Count Square Submatrices with All Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Square Submatrices with All Ones is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.

Problem statement

Given an m × n matrix of ones and zeros, return how many square submatrices consist entirely of ones. Squares of every size count, including 1 × 1.

Example 1

Input: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output: 15
Explanation: There are 10 squares of side 1, 4 of side 2 and 1 of side 3.

Example 2

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

Example 3

Input: matrix = [[1]]
Output: 1

Constraints

  • 1 <= matrix.length, matrix[i].length <= 8
  • matrix[i][j] is 0 or 1.

Hints for Count Square Submatrices with All Ones

  1. Hint 1

    Reuse the maximal-square recurrence: dp[r][c] is the side of the largest all-ones square ending at (r, c).

  2. Hint 2

    A cell with dp[r][c] = k is the bottom-right corner of exactly k squares — one of each side from 1 to k.

  3. Hint 3

    So the answer is the sum of the whole dp table, not its maximum.

How to solve Count Square Submatrices with All Ones

Reuse the maximal-square recurrence: a cell with dp = k is the bottom-right corner of exactly k all-ones squares (sides 1 … k), so the answer is the sum of the table.

Approach

  1. Compute dp[r][c] = 1 + min(up, left, up-left) for each 1-cell (1 on the border).
  2. Accumulate every dp[r][c].

Why it works

Every all-ones square has a unique bottom-right corner, and at that corner squares of every side up to the maximum exist, so summing the maximal sides counts every square exactly once.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Take the sum, not the maximum, of the table.

Reference solution

Python

def countSquares(matrix) -> int:
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    total = 0
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 1:
                if r == 0 or c == 0:
                    dp[r][c] = 1
                else:
                    dp[r][c] = min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1
                total += dp[r][c]
    return total

Java

public static int countSquares(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (matrix[r][c] == 1) {
                if (r == 0 || c == 0) dp[r][c] = 1;
                else dp[r][c] = Math.min(dp[r - 1][c], Math.min(dp[r][c - 1], dp[r - 1][c - 1])) + 1;
                total += dp[r][c];
            }
        }
    }
    return total;
}

C++

int countSquares(vector<vector<int>>& matrix) {
    int m = (int) matrix.size(), n = (int) matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (matrix[r][c] == 1) {
                if (r == 0 || c == 0) dp[r][c] = 1;
                else dp[r][c] = min(dp[r - 1][c], min(dp[r][c - 1], dp[r - 1][c - 1])) + 1;
                total += dp[r][c];
            }
        }
    }
    return total;
}

JavaScript

var countSquares = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const dp = [];
    for (let r = 0; r < m; r++) dp.push(new Array(n).fill(0));
    let total = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (matrix[r][c] === 1) {
                if (r === 0 || c === 0) dp[r][c] = 1;
                else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1;
                total += dp[r][c];
            }
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming