Count Square Submatrices with All Ones Medium 0 attempts
LeetCode ↗

Count Square Submatrices with All Ones

Medium Dynamic ProgrammingMemoization LeetCode

You're given a binary matrix of size m×n. Count every square-shaped submatrix, of any size, whose cells are entirely ones, and return the total count.

Input Format
Implement countSquares(matrix). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
matrix = [[0]]
Output
0
Constraints
  • 1 <= m, n <= 300
  • matrix[i][j] is 0 or 1
Test Cases (2)
Case 1
Args: [[[0,1,1,1],[1,1,1,1],[0,1,1,1]]] Expected: 15
Case 2
Args: [[[0]]] Expected: 0
Topics
Dynamic ProgrammingMemoization

DP

dp[i][j] = largest square ending at (i,j). Sum all dp values.

javascript
function countSquares(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let count = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] && i > 0 && j > 0) {
        matrix[i][j] = Math.min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1;
      }
      count += matrix[i][j];
    }
  }
  return count;
}

Time: O(mn) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript