Count Square Submatrices with All Ones

Slug: count-square-submatrices-with-all-ones

Difficulty: Medium

Id: 712541

Summary

Given a binary matrix, we need to count the number of square sub-matrices with all ones. This problem involves dynamic programming and optimization techniques.

Detailed Explanation

The given binary matrix can be thought of as a grid where each cell is either 0 or 1. We want to find the total count of square sub-matrices (of any size) that have only 1's in them. To solve this, we'll use dynamic programming.

Here is the step-by-step breakdown of the solution:

1. Initialize an array dp where dp[i][j] will store the count of all square sub-matrices ending at (i, j) with all ones.
2. Iterate over the matrix from top to bottom and left to right. For each cell (i, j), do the following:
   • If the current cell is 1 (i.e., matrix[i][j] == 1), then:
     • Update dp[i][j] = dp[i-1][j-1] + 1 if it's not the first row or column. This means we're considering a new square sub-matrix of size (k+1) starting from (i, j).
     • If it is the first row or column (i.e., i == 0 || j == 0), then set dp[i][j] = 1. This means we're considering a new square sub-matrix of size 1 (i.e., just this cell).
   • If the current cell is 0 (i.e., matrix[i][j] == 0), then set dp[i][j] = 0.
3. The total count of all square sub-matrices with all ones is stored in dp[m-1][n-1], where m and n are the dimensions of the input matrix.

Time complexity: O(mn) Space complexity: O(mn)

Optimized Solutions

Java