Count Square Submatrices with All Ones | Problems

Given a m×n binary matrix, return the total number of square submatrices that contain all ones.

Example: matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]] → Output: 15

Sample Input

—

Sample Output

—

Constraints

1 <= m, n <= 300
matrix[i][j] is 0 or 1

Test Cases

Case 1

Args: [[[0,1,1,1],[1,1,1,1],[0,1,1,1]]] Expected: 15

Topics

Dynamic Programming Memoization

DP

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

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.