LeetCode “Count Square Submatrices with All Ones” Problem Solution

LeetCode “Count Square Submatrices with All Ones” Problem Solution

44 / 100 SEO Score

Problem:

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

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.

There are 4 squares of side 2.

There is 1 square of side 3.

Total number of squares = 10 + 4 + 1 = 15

Example 2:

Input:

 matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

Output:

7

Explanation:

There are 6 squares of side 1.

There is 1 square of side 2.

Total number of squares = 6 + 1 = 7.

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

 

Solution:

For this problem solution, we will use Dynamic Programming, as you can see from the following drawing we have Overlapping Subproblems with Optimal Substructure which together form the perfect characteristic of any Dynamic Programming problem.

cache[i][j] represent the length of the biggest square whose lower-right corner element is matrix[i][j].  Also, there are cache[i][j] squares whose lower-right corner element are matrix[i][j].

As Figure, the square edge length ( whose lower-right corner element is matrix[i][j] ) is not greater than the minium of three items (top, above, diagonal) + 1. And when matrix[i][j]==0cache[i][j]=0.

LeetCode Count Square Submatrices with All Ones simulation

LeetCode Count Square Submatrices with All One’s simulation

 

Code:

public class CountSquareSubmatricesWithAllOnes {
  public int countSquares(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
      return 0;
    }

    int result = 0;
    int[][] cache = new int[matrix.length][matrix[0].length];

    // initialize first column of the cache object
    for(int i = 0; i < matrix.length; i++){
      cache[i][0] = matrix[i][0];
      result += cache[i][0];
    }

    // initialize first row of the cache object
    for(int i = 1; i < matrix[0].length; i++){
      cache[0][i] = matrix[0][i];
      result += cache[0][i];
    }

    for(int i = 1; i < matrix.length; i++){
      for(int j = 1; j < matrix[0].length; j++){
        if(matrix[i][j] == 1){
          cache[i][j] = Math.min(Math.min(cache[i - 1][j-1], cache[i - 1][j]), cache[i][j-1]) + 1;
          result += cache[i][j];
        }
      }
    }

    return result;
  }

  public static void main(String[] args) {
    int[][] matrix = new int[][]{
        {0, 1, 1, 1},
        {1, 1, 1, 1},
        {0, 1, 1, 1}
    };
    CountSquareSubmatricesWithAllOnes cs = new CountSquareSubmatricesWithAllOnes();
    assert cs.countSquares(matrix) == 15;
  }
}

Complexity Analysis:

  • Time: O(nm)
  • Space: O(nm)

Leave a Reply