Count Square Submatrices with All Ones

Introduction to the problem statement

Today's task is to obtain all of the possible squares in the provided matrix. Before we get started, the question we'll be looking up today is similar to the one we looked up previously, Maximal Square.

Since today’s problem is based on dynamic programming, it is recommended to have basic knowledge of it for better understanding.

Now, let's go into the specifics of the problem:

The problem says:-

Given an 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.

Example 3:-

Input: matrix=
[
[1]
]

Output: 1

Explanation:

There is 1 square of side 1.

Total number of squares = 1

Example 4:-

Input: matrix=
[
[0]
]

Output: 0

Explanation:

Square can not be formed using 0’s.

Total number of squares = 0

Example 5:

Input: matrix=
[ ]

Output: 0

Explanation:

Empty matrix.

Let us now discuss the idea:

The idea is to simply traverse the matrix from the last element to the first element, treating each traversed element as a top-left square element and counting how many squares can be made using each element.

Let us now have a look at the Algorithm:

Algorithm

Step 1:- Make a function countSquares( matrix[][] ), which accepts a matrix and returns the final count of the squares.

Step 1.1:- Inside the function, initialize the count as 0.

Step 1.2:- Declare the auxiliary matrix with the same size as the passed matrix.

Suppose the user provides the below matrix:-

Thus, the auxiliary matrix will look like the following:-

Step 1.3:- Traverse through the passed matrix from the last index until the pointer reaches the first index.

Step 1.3.1:- Add each traversed element to the auxiliary matrix( dp[][] ).

Step 1.3.2:- Increment the count each time when the traversed element is 1.

Step 1.3.3:- For each traversed element check whether it lies outside the last row or last column,

If yes, find the minimum element from the current element’s next, bottom, and diagonal element of the dp[ ] [ ] matrix.

Add 1 to the minimum element and overwrite the prewritten value in dp[][] matrix.

Step 1.3.4:- Check if the overwritten value is greater than 1 or not. If yes, then update the count.

count -> count + (dp[i][j]-1)

Step 1.4:- Return the count to the respected function call.

Pseudo Code

int countSquares(matrix[][])
Initialize the count as 0
count -> 0
int rows = matrix.size()
int cols = matrix[0].size()
int dp[rows][cols]

for(int i=rows-1 ; i>=0 ;i--)
for(int j=cols-1 ; j>=0; j--)

dp[i][j] = matrix[i][j]
if(dp[i][j] == 1)
count -> count + 1

if(i < rows-1 && j < cols-1 && matrix[i][j]!=0)

dp[i][j] = 1 + min(min(dp[i][j+1] , dp[i+1][j]), dp[i+1][j+1])
if(dp[i][j] > 1)
count -> count + (dp[i][j]-1)

return count

Implementation in Java

// Java program to count square submatrices with all ones

import java.io.*;
import java.util.*;
public class CountSquaresSubmatrices {
public static int countSquares(int[][] matrix) {
  // there can be a case where the matrix has no elements
  int count = 0;
  // take how many numbers of rows are there
  int rows = matrix.length;
  // take how many numbers of columns are there
  int cols = matrix[0].length;
  // define an auxiliary matrix to keep track of the formation of squares
  int[][] dp = new int[rows][cols];

  // traverse the passed matrix from the last element until it reaches the first element

  for(int i = rows-1; i>=0; i--){
  for(int j = cols-1; j>=0; j--){

// store each element being traversed into the auxiliary matrix
dp[i][j] = matrix[i][j];
  // If the current index of auxiliary matrix holding the 1's, increment the count by 1
  if(dp[i][j] == 1){
  count++;
}
  // Overwrite those values which are not in the last row or last columns
  if(i<rows-1 && j<cols-1 && matrix[i][j]!=0){

// find the minimum among the current index's next element, bottom element, and diagonal element of dp[][]
  // and update dp[][] matrix with the minimum value + 1.
dp[i][j] = 1 + Math.min(Math.min(dp[i+1][j] , dp[i][j+1]), dp[i+1][j+1] );

  // there can be a case of formation of the large square, i.e., more than 1 side,
  // if that is so, update the count
  // for example:- if the dp[i][j] contains "2"
  // it means [ 1 , 1 ]
  // [ 1 , 1 ], they all are forming 1 side of square individually, and together they are forming a square of side 2
  // hence, count is updated by (dp[i][j]-1) or (2-1)= 1 in this example.
  if(dp[i][j] > 1){
  count = count + (dp[i][j] - 1);
}
}
}
}
  // return the count to the function call
  return count;
}
public static void main(String[] args) {
  // Scanner class to take the input from the user
Scanner scn = new Scanner(System.in);
System.out.println("Enter the number of rows: ");
  int rows = scn.nextInt();
System.out.println("Enter the number of cols: ");
  int cols = scn.nextInt();

  int[][] arr = new int[rows][cols];

System.out.println("Enter the elements :-> ");
  for (int i = 0; i < rows; i++) {
  for (int j = 0; j < cols; j++) {
arr[i][j] = scn.nextInt();
}
}
  // function call
System.out.println("Count Squares Sub matrices with all ones :- " + countSquares(arr));
}
}

Input Test Case:-

Enter the rows :
4
Enter the columns :
3
Enter the elements :
0 1 1
1 1 0
1 1 1
0 0 1

Output

Count Square Submatrices with all ones: 9

Implementation in C++

// c++ program to count square submatrices with all ones
#include <bits/stdc++.h>
using namespace std;

int countSquares(vector<vector<int>>& matrix) {
  // there can be a case where the matrix has no elements
  int count = 0;
  // take how many numbers of rows are there
  int rows = matrix.size();
  // take how many numbers of columns are there
  int cols = matrix[0].size();
  // define an auxiliary matrix to keep track of the formation of squares
  int dp[rows][cols];

  // traverse the passed matrix from the last element until it reaches the first element
  for(int i=rows-1 ; i>=0 ;i--){
  for(int j=cols-1 ; j>=0; j--){
  // store each element being traversed into the auxiliary matrix
dp[i][j] = matrix[i][j];
  // If the current index of auxiliary matrix holding the 1's, increment the count by 1
  if(dp[i][j] == 1){
count++;
}

  // Overwrite those values which are not in the last row or last columns
  if(i < rows-1 && j < cols-1 && matrix[i][j]!=0){

  // find the minimum among the current index's next element, bottom element, and diagonal element of dp[][]
  // and update dp[][] matrix with the minimum value + 1.
dp[i][j] = 1 + min(min(dp[i][j+1] , dp[i+1][j]), dp[i+1][j+1]);

  // there can be a case of formation of the large square, i.e., more than 1 side,
  // if that is so, update the count
  // for example:- if the dp[i][j] contains "2"
  // it means [ 1 , 1 ]
  // [ 1 , 1 ], they all are forming 1 side of square individually, and together they are forming a square of side 2
  // hence, count is updated by (dp[i][j]-1) or (2-1)= 1 in this example.
  if(dp[i][j] > 1){
count = count + (dp[i][j]-1);
}
}
}
}
  // return the count to the function call
  return count;
}
int main() {
  // declare the multi dimensional vector
  vector<vector<int>> v ;
  int rows, cols, temp;
  cout<<"Enter the rows :"<<endl;
  cin>>rows;
  cout<<"Enter the columns :"<<endl;
  cin>>cols;
  cout<<"Enter the elements : "<<endl;

  // take the input from the user
  for(int i=0 ;i<rows ;i++){
  vector<int> x;
  for(int j=0 ; j<cols ; j++){
  cin>>temp;
x.push_back(temp);
}
v.push_back(x);
}
  // functional call
  cout<<"Count Square Submatrices with all ones : "<<countSquares(v);
  return 0;
}

Input Test Case:-

Enter the rows :
3
Enter the columns :
3
Enter the elements :
1 1 0
0 1 1
1 1 1

Output

Count Square Submatrices with all ones: 8

Complexity Analysis of Count Square Submatrices with All Ones

Time Complexity: O(rows*cols), where rows and cols are the total number of rows and the columns in a matrix.

Space Complexity: O(rows*cols), as we initialized the additional matrix with the same size of the given matrix.

Frequently asked questions

What is memoization in dynamic programming?
Memoization is a standard methodology for dynamic programming problems. The answer is solutions to the same problem with smaller inputs (like in the Fibonacci problem).
What are the applications of dynamic programming?
0/1 knapsack problem
Mathematical optimization problem
All pair shortest path problem
Time-sharing: It schedules the job to maximize CPU usage
Reliability design problem
Longest common subsequence (LCS)
Flight control and robotics control

What is the difference between the feasible solution and optimal solution?
A feasible solution meets all of the constraints of the problem. When maximizing, an optimal solution is a feasible solution that yields the highest attainable objective function value (or smallest when minimizing).
What makes dynamic programming better than others?
Dynamic programming allows for less repetitive work and, as a result, higher runtime efficiency. It is worth noting that dynamic programming fundamentally trades space efficiency for time efficiency, as solution storing necessitates space that is not required in brute force recursive solutions.

Key takeaways

To wrap up the session, we’ve looked upon one more question often asked in interviews, i.e., Count Submatrices with All Ones. We’ve also analyzed the complexity of the approach. Continue to try such questions to have a better knowledge of Dynamic programming. Other approaches may have been used to tackle the situation, but they resulted in much more complexities. Understanding Dynamic programming principles is critical since it is the most frequently asked question during interviews.

Nonetheless, if you continue to attempt such questions and stick to the guided path, you can easily ace your interview.

There are several resources available on the market, but a well-structured strategy is all that is required. Right?

As a result, check out our top-tier courses taught by the greatest teachers and have fun coding.