Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Example 1
2.1.1.
Input
2.1.2.
Output 
2.2.
Explanation 
2.3.
Example 2
2.3.1.
Input 
2.3.2.
Output 
2.4.
Explanation
3.
Approach
4.
Algorithm
5.
Dry Run
5.1.
Implementation in Java
5.1.1.
Output
5.2.
Implementation in C++
5.2.1.
Output
6.
Frequently Asked Questions
6.1.
What is memoisation in dynamic programming?
6.2.
What are the applications of dynamic programming?
6.3.
What is the difference between the feasible solution and the optimal solution?
6.4.
What does the optimality principle imply in dynamic programming?
6.5.
What makes dynamic programming better than others?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count Square Submatrices with All Ones

Author Alisha Chhabra
2 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

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.

Count Square Submatrices with All Ones

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:

Problem Statement

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

Example 1

Input

 matrix =

example 1


Output 

10

Explanation 

There are 8 squares of side 1.

explanation

There are four squares on side 2.

Explanation

There is 0 square on side 3.

Total number of squares = 8 + 2 + 0 = 10.

Example 2

Input 

matrix = 

example 2

Output 

21

Explanation

There are 13 squares of side 1.

Explanation

 

There is 6 square of side 2. 

Explanation
Explanation

There is 2 square of side 3. 

Explanation

Total number of squares = 13 + 6 + 2 = 21.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

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:

Also Read About, Array Implementation of Queue and  Rabin Karp 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:-

Algorithm

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

auxiliary matrix

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

Algorithm


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

Algorithm

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,

Algorithm

                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.

Dry Run

arr = {{1,1,1,1}, {1,1,0,1}, {0,1,0,1}}:

  • Define count to be 0.
     
  • Get the number of rows and columns in the input matrix arr.

    • rows = 3 (number of rows in arr)
       
    • cols = 4 (number of columns in arr)
       
  • Define a new auxiliary matrix dp with the same number of rows and columns as the input matrix arr.

    • dp = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}

       
  • Traverse the input matrix arr from the last element to the first element.
     
Dry Run
  • And count increase one more for 2x2 matrix.
     
  • Total count is 10
Dry Run

Implementation in Java


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) {
        // Hardcoded input:
        int[][] arr = {{1,1,1,1}, {1,1,0,1}, {0,1,0,1}};

        // function call
        System.out.println("Count Squares Sub matrices with all ones :- " + countSquares(arr));
    }
}

Output

output

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 { {1, 1, 1, 1}, {1, 1, 0, 1}, {0, 1, 0, 1} };
    
    // functional call
    cout<<"Count Square Submatrices with all ones : "<<countSquares(v);
    return 0;
}

Output

Output

 

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 initialised the additional matrix with the same size of the given matrix.

Frequently Asked Questions

What is memoisation in dynamic programming?

Memoisation 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?

Here are some problems: 0/1 knapsack problem, Mathematical optimisation problem, All pair shortest path problem, Time-sharing: It schedules the job to maximise CPU usage, Reliability design problem, Longest common subsequence (LCS), Flight control and robotics control.

What is the difference between the feasible solution and the optimal solution?

A feasible solution meets all of the constraints of the problem. When maximising, an optimal solution is a feasible solution that yields the highest attainable objective function value (or smallest when minimising).

What does the optimality principle imply in dynamic programming?

Dynamic programming uses the optimality principle to solve complex problems by breaking them into smaller subproblems, solving each subproblem optimally, and combining their solutions.

What makes dynamic programming better than others?

Dynamic programming reduces repetition and increases runtime efficiency by trading space for time. Solution storing takes up space not needed in recursive solutions.

Conclusion

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.

Previous article
Shuffle an array using Fisher-Yates shuffle Algorithm
Next article
Matrix probability problem
Live masterclass