Search⌘ K
Home
Courses
Grokking Dynamic Programming Interview

Count Square Submatrices

Explore how to count square submatrices containing only ones in a binary matrix using dynamic programming. Understand naive, top-down, and bottom-up approaches and optimize space and time complexity. This lesson helps develop techniques to solve matrix-based DP problems effectively.

We'll cover the following...

Statement

Given a matrix containing only ones and zeros, count the total number of square submatrices that contain only ones.

If the matrix is empty, then return 0.

Constraints:

  • 1<=1 <= matrix.length <=2000<= 2000
  • 1<=1 <= matrix[i].length <=2000<= 2000
  • matrix[i][j] is either 00 or 11

Examples

No.

Matrix

Square Submatrices with all Ones



1

[

[1, 0, 1]

[1, 1, 0]

[1, 1, 0]

]



7



2

[

[1, 1, 1],

[1, 1, 1],

[1, 1, 1]

]



14

Try it yourself

Implement your solution in the following playground.

Java
usercode > CountSquares.java
import java.util.*;
class CountSquareSubmatrices {
    public static int countSquares(int[][] matrix) {
        // your code will replace the placeholder return statement below
        return -1;
    }
}
Count Square Submatrices

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 knapsack dynamic programming pattern.

Naive approach

The naive approach would be to iterate over all the square submatrices and check if they contain all ones.

We iterate over the entire matrix and at each cell, we check if the value is 00 or 11. If the value is 11, we call the helper function which ...