Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview in C++

Count Square Submatrices

Explore how to count all square submatrices filled with ones in a binary matrix by applying dynamic programming techniques. Understand the naive recursive method and then improve it with top-down memoization and bottom-up tabulation approaches. Gain insight into optimizing both time and space complexity by storing results within the input matrix, preparing you to tackle similar coding interview challenges.

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 <=200<= 200
  • 1<=1 <= matrix[i].length <=200<= 200
  • 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.

C++
usercode > CountSquares.cpp
int CountSquares(std::vector< std::vector<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 ...