Given an N*M matrix containing only 0s and 1s, the task is to count the number of square submatrices containing all 1s.
Examples:
Input: arr[][] = {{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 1, 1, 1}}
Output: 15
Explanation:
There are 10 squares of side length 1.
There are 4 squares of side length 2.
There is 1 square of side length 3.
Total number of squares = 10 + 4 + 1 = 15.
Input: arr[][] = {{1, 0, 1},
{1, 1, 0},
{1, 1, 0}}
Output: 7
Naive Recursion Approach:
- At every position, we determine the maximum possible side length for a square if we consider that position as the top left corner. This maximum length can also contain smaller squares with lengths 2 and 1.
- Therefore, we can calculate the total number of squares by adding these lengths to our final answer.
- In summary, we can state that the largest square with coordinates (i,j) as the top left corner is equal to the total count of squares with (i,j) as the top left corner.
C++
// C++ program to return the number of// square submatrices with all 1s#include <bits/stdc++.h>using namespace std;// Function to solve the problem recursivelyint solve(vector<vector<int> >& matrix, int m, int n, int i, int j){ // Base case: if out of bounds or current element is 0 if (i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] == 0) { return 0; } // Recursive calls to calculate the number of squares in // right, bottom, and bottom-right directions int right = solve(matrix, m, n, i, j + 1); int bottom = solve(matrix, m, n, i + 1, j); int bottom_right = solve(matrix, m, n, i + 1, j + 1); // Return the count of squares for the current position return 1 + min({ right, bottom, bottom_right });}// Function to return the number of square submatrices with// all 1sint countSquareMatrices(vector<vector<int> >& matrix){ int m = matrix.size(); int n = matrix[0].size(); int ans = 0; // Iterate over each element of the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { // If current element is 1, recursively // calculate the number of squares and add // it to the answer ans += solve(matrix, m, n, i, j); } } } // Return the final answer return ans;}// Driver codeint main(){ vector<vector<int> > arr = { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; cout << countSquareMatrices(arr); return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class SquareSubmatrices { // Function to solve the problem recursively static int solve(List<List<Integer>> matrix, int m, int n, int i, int j) { // Base case: if out of bounds or current element is 0 if (i < 0 || i >= m || j < 0 || j >= n || matrix.get(i).get(j) == 0) { return 0; } // Recursive calls to calculate the number of squares in right, bottom, and bottom-right directions int right = solve(matrix, m, n, i, j + 1); int bottom = solve(matrix, m, n, i + 1, j); int bottomRight = solve(matrix, m, n, i + 1, j + 1); // Return the count of squares for the current position return 1 + Math.min(Math.min(right, bottom), bottomRight); } // Function to return the number of square submatrices with all 1s static int countSquareMatrices(List<List<Integer>> matrix) { int m = matrix.size(); int n = matrix.get(0).size(); int ans = 0; // Iterate over each element of the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix.get(i).get(j) == 1) { // If current element is 1, recursively calculate the number of squares and add it to the answer ans += solve(matrix, m, n, i, j); } } } // Return the final answer return ans; } // Driver code public static void main(String[] args) { List<List<Integer>> arr = new ArrayList<>(); arr.add(List.of(1, 0, 1)); arr.add(List.of(1, 1, 0)); arr.add(List.of(1, 1, 0)); System.out.println(countSquareMatrices(arr)); }} |
Python3
def solve(matrix, m, n, i, j): # Base case: if out of bounds or current element is 0 if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] == 0: return 0 # Recursive calls to calculate the number of squares in right, bottom, and bottom-right directions right = solve(matrix, m, n, i, j + 1) bottom = solve(matrix, m, n, i + 1, j) bottom_right = solve(matrix, m, n, i + 1, j + 1) # Return the count of squares for the current position return 1 + min(right, bottom, bottom_right)def countSquareMatrices(matrix): m = len(matrix) n = len(matrix[0]) ans = 0 # Iterate over each element of the matrix for i in range(m): for j in range(n): if matrix[i][j] == 1: # If current element is 1, recursively calculate the number of squares and add it to the answer ans += solve(matrix, m, n, i, j) # Return the final answer return ans# Driver codearr = [[1, 0, 1], [1, 1, 0], [1, 1, 0]]print(countSquareMatrices(arr)) |
C#
using System;using System.Collections.Generic;public class GFG{ // Function to solve the problem recursively public static int Solve(List<List<int>> matrix, int m, int n, int i, int j) { // Base case: if out of bounds or current element is 0 if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 0) { return 0; } // Recursive calls to calculate the number of squares in // right, bottom, and bottom-right directions int right = Solve(matrix, m, n, i, j + 1); int bottom = Solve(matrix, m, n, i + 1, j); int bottom_right = Solve(matrix, m, n, i + 1, j + 1); // Return the count of squares for the current position return 1 + Math.Min(Math.Min(right, bottom), bottom_right); } // Function to return the number of square submatrices with all 1s public static int CountSquareMatrices(List<List<int>> matrix) { int m = matrix.Count; int n = matrix[0].Count; int ans = 0; // Iterate over each element of the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { // If current element is 1, recursively calculate // the number of squares and add it to the answer ans += Solve(matrix, m, n, i, j); } } } // Return the final answer return ans; } // Driver code public static void Main(string[] args) { List<List<int>> arr = new List<List<int>>() { new List<int>() { 1, 0, 1 }, new List<int>() { 1, 1, 0 }, new List<int>() { 1, 1, 0 } }; Console.WriteLine(CountSquareMatrices(arr)); }} |
Output
7
Time Complexity: O(2N*M)
Auxiliary Space: O(1)
An approach using Top Down DP/ Memoization:
Memoization is used in this problem to optimize the solution by avoiding redundant calculations. Since we are making recursive calls to solve subproblems, there can be overlapping subproblems where the same submatrix is being computed multiple times. By using memoization, we can store the results of subproblems in a table (in this case, the dp table) and reuse them when needed. When a subproblem is encountered again, instead of recomputing its value, we can simply retrieve it from the table. This greatly reduces the number of redundant calculations and improves the overall efficiency of the algorithm.
In the provided code, the dp table is a 2D vector that stores the computed results for each position in the matrix. Before making a recursive call, the function checks if the value for the current position is already present in the dp table. If so, it directly returns that value instead of recomputing it.
Using memoization ensures that each subproblem is solved only once, leading to a significant reduction in the number of recursive calls and improving the overall time complexity of the solution.
Below is the implemenation of the above approach:
C++
// C++ program to return the number of// square submatrices with all 1s#include <bits/stdc++.h>using namespace std;// Recursive function to solve the problemint solve(vector<vector<int> >& matrix, int m, int n, int i, int j, vector<vector<int> >& dp){ // Base case: if out of bounds or current element is 0 if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 0) { return 0; } // If the value is already calculated, return it from dp // table if (dp[i][j] != -1) return dp[i][j]; // Recursive calls to calculate the number of squares in // right, bottom, and bottom-right directions int right = solve(matrix, m, n, i, j + 1, dp); int bottom = solve(matrix, m, n, i + 1, j, dp); int bottom_right = solve(matrix, m, n, i + 1, j + 1, dp); // Memoize the calculated value and return it return dp[i][j] = 1 + min({ right, bottom, bottom_right });}// Function to return the number of square submatrices with// all 1sint countSquareMatrices(vector<vector<int> >& matrix){ int m = matrix.size(); int n = matrix[0].size(); // Create a dp table to store the results of subproblems vector<vector<int> > dp(m + 1, vector<int>(n + 1, -1)); int ans = 0; // Iterate over each element of the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { // If the current element is 1, recursively // calculate the number of squares and add // it to the answer ans += solve(matrix, m, n, i, j, dp); } } } // Return the final answer return ans;}// Driver codeint main(){ vector<vector<int> > arr = { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; cout << countSquareMatrices(arr); return 0;} |
Java
import java.util.*;public class SquareSubmatrices { // Recursive function to solve the problem static int solve(int[][] matrix, int m, int n, int i, int j, int[][] dp) { // Base case: if out of bounds or current element is // 0 if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 0) { return 0; } // If the value is already calculated, return it // from dp table if (dp[i][j] != -1) return dp[i][j]; // Recursive calls to calculate the number of // squares in right, bottom, and bottom-right // directions int right = solve(matrix, m, n, i, j + 1, dp); int bottom = solve(matrix, m, n, i + 1, j, dp); int bottomRight = solve(matrix, m, n, i + 1, j + 1, dp); // Memoize the calculated value and return it return dp[i][j] = 1 + Math.min(Math.min(right, bottom), bottomRight); } // Function to return the number of square submatrices // with all 1s static int countSquareMatrices(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; // Create a dp table to store the results of // subproblems int[][] dp = new int[m + 1][n + 1]; for (int[] row : dp) { Arrays.fill(row, -1); } int ans = 0; // Iterate over each element of the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { // If the current element is 1, // recursively calculate the number of // squares and add it to the answer ans += solve(matrix, m, n, i, j, dp); } } } // Return the final answer return ans; } // Driver code public static void main(String[] args) { int[][] arr = { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; System.out.println(countSquareMatrices(arr)); }} |
Python3
# Recursive function to solve the problemdef solve(matrix, m, n, i, j, dp): # Base case: if out of bounds or current element is 0 if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] == 0: return 0 # If the value is already calculated, return it from dp table if dp[i][j] != -1: return dp[i][j] # Recursive calls to calculate the number of squares in right, bottom, and bottom-right directions right = solve(matrix, m, n, i, j + 1, dp) bottom = solve(matrix, m, n, i + 1, j, dp) bottom_right = solve(matrix, m, n, i + 1, j + 1, dp) # Memoize the calculated value and return it dp[i][j] = 1 + min(right, bottom, bottom_right) return dp[i][j]# Function to return the number of square submatrices with all 1sdef countSquareMatrices(matrix): m = len(matrix) n = len(matrix[0]) # Create a dp table to store the results of subproblems dp = [[-1] * (n + 1) for _ in range(m + 1)] ans = 0 # Iterate over each element of the matrix for i in range(m): for j in range(n): if matrix[i][j] == 1: # If the current element is 1, recursively calculate the number of squares and add it to the answer ans += solve(matrix, m, n, i, j, dp) # Return the final answer return ans# Driver codearr = [[1, 0, 1], [1, 1, 0], [1, 1, 0]]print(countSquareMatrices(arr)) |
C#
using System;public class GFG{ // Recursive function to solve the problem public static int Solve(int[][] matrix, int m, int n, int i, int j, int[][] dp) { // Base case: if out of bounds or current element is 0 if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 0) { return 0; } // If the value is already calculated, return it from dp table if (dp[i][j] != -1) return dp[i][j]; // Recursive calls to calculate the number of squares in right, // bottom, and bottom-right directions int right = Solve(matrix, m, n, i, j + 1, dp); int bottom = Solve(matrix, m, n, i + 1, j, dp); int bottomRight = Solve(matrix, m, n, i + 1, j + 1, dp); // Memoize the calculated value and return it return dp[i][j] = 1 + Math.Min(right, Math.Min(bottom, bottomRight)); } // Function to return the number of square submatrices with all 1s public static int CountSquareMatrices(int[][] matrix) { int m = matrix.Length; int n = matrix[0].Length; // Create a dp table to store the results of subproblems int[][] dp = new int[m + 1][]; for (int i = 0; i <= m; i++) { dp[i] = new int[n + 1]; for (int j = 0; j <= n; j++) { dp[i][j] = -1; } } int ans = 0; // Iterate over each element of the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { // If the current element is 1, recursively // calculate the number of squares and add it to the answer ans += Solve(matrix, m, n, i, j, dp); } } } // Return the final answer return ans; } // Driver code public static void Main(string[] args) { int[][] arr = new int[][] { new int[] { 1, 0, 1 }, new int[] { 1, 1, 0 }, new int[] { 1, 1, 0 } }; Console.WriteLine(CountSquareMatrices(arr)); }} |
Output
7
Time Complexity: O(N*M)
Auxiliary Space: O(1)
An approach using Buttom-Up:
This problem can be solved using Dynamic Programming.
- Let the array arr[i][j] store the number of square matrices ending at (i, j)
- The recurrence relation to find the number of squares ending at (i, j) can be given by:
- If arr[i][j] is 1:
- arr[i][j] = min( min(arr[i-1][j], arr[i][j-1]), arr[i-1][j-1]) + 1
- Else if arr[i][j] is 0:
- arr[i][j] = 0
- If arr[i][j] is 1:
- Calculate the sum of the array which is equal to the number of square submatrices with all 1s.
Below is the implementation of the above approach:
CPP
// C++ program to return the number of// square submatrices with all 1s#include <bits/stdc++.h>using namespace std;#define n 3#define m 3// Function to return the number of// square submatrices with all 1sint countSquareMatrices(int a[][m], int N, int M){ // Initialize count variable int count = 0; for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If a[i][j] is equal to 0 if (a[i][j] == 0) continue; // Calculate number of // square submatrices // ending at (i, j) a[i][j] = min(min(a[i - 1][j], a[i][j - 1]), a[i - 1][j - 1]) + 1; } } // Calculate the sum of the array for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) count += a[i][j]; return count;}// Driver codeint main(){ int arr[][m] = { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; cout << countSquareMatrices(arr, n, m); return 0;} |
Java
// Java program to return the number of // square submatrices with all 1sclass GFG { final static int n = 3; final static int m = 3; // Function to return the number of // square submatrices with all 1s static int countSquareMatrices(int a[][], int N, int M) { // Initialize count variable int count = 0; for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If a[i][j] is equal to 0 if (a[i][j] == 0) continue; // Calculate number of // square submatrices // ending at (i, j) a[i][j] = Math.min(Math.min(a[i - 1][j], a[i][j - 1]), a[i - 1][j - 1]) + 1; } } // Calculate the sum of the array for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) count += a[i][j]; return count; } // Driver code public static void main (String[] args) { int arr[][] = { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; System.out.println(countSquareMatrices(arr, n, m)); } }// This code is contributed by AnkitRai01 |
Python
# Python3 program to return the number of# square submatrices with all 1sn = 3m = 3# Function to return the number of# square submatrices with all 1sdef countSquareMatrices(a, N, M): # Initialize count variable count = 0 for i in range(1, N): for j in range(1, M): # If a[i][j] is equal to 0 if (a[i][j] == 0): continue # Calculate number of # square submatrices # ending at (i, j) a[i][j] = min([a[i - 1][j], a[i][j - 1], a[i - 1][j - 1]])+1 # Calculate the sum of the array for i in range(N): for j in range(M): count += a[i][j] return count# Driver codearr = [ [ 1, 0, 1], [ 1, 1, 0 ], [ 1, 1, 0 ] ]print(countSquareMatrices(arr, n, m))# This code is contributed by mohit kumar 29 |
C#
// C# program to return the number of // square submatrices with all 1susing System;class GFG { static int n = 3; static int m = 3; // Function to return the number of // square submatrices with all 1s static int countSquareMatrices(int [,]a, int N, int M) { // Initialize count variable int count = 0; for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If a[i][j] is equal to 0 if (a[i, j] == 0) continue; // Calculate number of // square submatrices // ending at (i, j) a[i, j] = Math.Min(Math.Min(a[i - 1, j], a[i, j - 1]), a[i - 1, j - 1]) + 1; } } // Calculate the sum of the array for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) count += a[i, j]; return count; } // Driver code public static void Main() { int [,]arr = { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; Console.WriteLine(countSquareMatrices(arr, n, m)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to return the number of// square submatrices with all 1svar n = 3var m = 3// Function to return the number of// square submatrices with all 1sfunction countSquareMatrices(a, N, M){ // Initialize count variable var count = 0; for (var i = 1; i < N; i++) { for (var j = 1; j < M; j++) { // If a[i][j] is equal to 0 if (a[i][j] == 0) continue; // Calculate number of // square submatrices // ending at (i, j) a[i][j] = Math.min(Math.min(a[i - 1][j], a[i][j - 1]), a[i - 1][j - 1]) + 1; } } // Calculate the sum of the array for (var i = 0; i < N; i++) for (var j = 0; j < M; j++) count += a[i][j]; return count;}// Driver codevar arr = [ [ 1, 0, 1 ], [ 1, 1, 0 ], [ 1, 1, 0 ] ];document.write( countSquareMatrices(arr, n, m));</script> |
Output
7
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
