Posted on by Kalkicode
Code Matrix

# Count square submatrices with all ones

The problem is to count the number of square submatrices with all ones in a given 2D matrix. A square submatrix is a contiguous submatrix with all its elements being ones.

## Example

Consider the following 2D matrix:

``````0 1 0 1 1 0
0 1 1 1 1 1
1 1 1 1 1 1
1 0 1 1 1 1``````

The number of square submatrices with all ones in this matrix is 29.

## Idea to Solve the Problem

To count the number of square submatrices with all ones, we can use dynamic programming. We will create an auxiliary matrix with the same dimensions as the input matrix. Each cell in the auxiliary matrix will represent the size of the largest square submatrix with all ones that ends at that cell.

## Algorithm

1. Create an auxiliary matrix of the same dimensions as the input matrix, initialized with all zeroes.
2. Traverse the first row and the first column of the input matrix. For each element in the first row or the first column that is equal to 1, update the corresponding cell in the auxiliary matrix to 1 and add 1 to the result variable.
3. For each cell (i, j) in the input matrix (excluding the first row and first column): a. If the current cell (i, j) is equal to 1:
• Set the value of the corresponding cell in the auxiliary matrix (i, j) to the minimum of the values of the three adjacent cells (i, j-1), (i-1, j-1), and (i-1, j) in the auxiliary matrix, and add 1 to it. This represents the size of the largest square submatrix with all ones that ends at the current cell.
• Add the value of the current cell in the auxiliary matrix to the result variable. b. If the current cell (i, j) is equal to 0, set the value of the corresponding cell in the auxiliary matrix to 0.

## Pseudocode

``````countSquareOnce(matrix):
row = number of rows in matrix
col = number of columns in matrix
Create an auxiliary matrix of size row x col initialized with all zeroes
result = 0
Traverse the first row and the first column of the matrix:
if the current cell is 1:
set the corresponding cell in the auxiliary matrix to 1
increment result by 1
for i from 1 to row-1:
for j from 1 to col-1:
if matrix[i][j] is 1:
auxiliary[i][j] = minimum(auxiliary[i][j-1], auxiliary[i-1][j-1], auxiliary[i-1][j]) + 1
increment result by auxiliary[i][j]
print the value of result as the total number of square submatrices with all ones``````

## Code Solution

``````// C Program
// Count square submatrices with all ones

#include <stdio.h>

// Matrix size
#define R 4
#define C 6

// Returns the minimum value of given two numbers (integer)
int minimum(int a,int b)
{
if(a > b)
{
return b;
}
else
{
return a;
}

}

//count number of square submatrices with all 1s
void countSquareOnce(int matrix[R][C])
{

// Auxiliary matrix which is used to find and store all square matrix
int auxiliary[R][C];

// Loop controllong variables
int i = 0;
int j = 0;

int result = 0;

// Set first element of each rows
for (i = 0; i < R; ++i)
{
auxiliary[i][0] = matrix[i][0];
result += matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < C; ++j)
{
auxiliary[0][j] = matrix[0][j];

result += matrix[0][j];
}

for (i = 1; i < R; ++i)
{

for (j = 1; j < C; ++j)
{

if(matrix[i][j]==1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i][j] =  minimum(minimum(auxiliary[i][j-1],auxiliary[i-1][j-1]), auxiliary[i-1][j])+1;
}
else
{
auxiliary[i][j] = matrix[i][j];
}

result += auxiliary[i][j];
}
}

printf("\n Total Square submatrix of 1's is : %d \n",result);

}

int main(int argc, char const *argv[])
{
// Define matrix of integer element which contains (0 and 1)
int matrix[R][C] =
{
{0,1,0,1,1,0},
{0,1,1,1,1,1},
{1,1,1,1,1,1},
{1,0,1,1,1,1}
};

countSquareOnce(matrix);

return 0;
}``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````/*
Java Program for
Count square submatrices with all ones
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
public int minimum(int a, int b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
public void countSquareOnce(int[][] matrix)
{
int row = matrix.length;
int col = matrix[0].length;
// Auxiliary matrix which is used to find and store all square matrix
int[][] auxiliary = new int[row][col];
// Loop controllong variables
int i = 0;
int j = 0;
int result = 0;
// Set first element of each rows
for (i = 0; i < row; ++i)
{
auxiliary[i][0] = matrix[i][0];
result += matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < col; ++j)
{
auxiliary[0][j] = matrix[0][j];
result += matrix[0][j];
}
for (i = 1; i < row; ++i)
{
for (j = 1; j < col; ++j)
{
if (matrix[i][j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i][j] = minimum(minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
}
else
{
auxiliary[i][j] = matrix[i][j];
}
result += auxiliary[i][j];
}
}
System.out.print("\n Total Square submatrix of 1's is : " + result + " \n");
}
public static void main(String[] args)
{
// Define matrix of integer element which contains (0 and 1)
int[][] matrix =
{
{
0 , 1 , 0 , 1 , 1 , 0
},
{
0 , 1 , 1 , 1 , 1 , 1
},
{
1 , 1 , 1 , 1 , 1 , 1
},
{
1 , 0 , 1 , 1 , 1 , 1
}
};
}
}``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````// Include header file
#include <iostream>
// Matrix size
#define R 4
#define C 6

using namespace std;

/*
C++ Program for
Count square submatrices with all ones
*/

class SquareSubmatrix
{
public:
// Returns the minimum value of given two numbers (integer)
int minimum(int a, int b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
void countSquareOnce(int matrix[R][C])
{

// Auxiliary matrix which is used to find and store all square matrix
int auxiliary[R][C];
// Loop controllong variables
int i = 0;
int j = 0;
int result = 0;
// Set first element of each rows
for (i = 0; i < R; ++i)
{
auxiliary[i][0] = matrix[i][0];
result += matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < C; ++j)
{
auxiliary[0][j] = matrix[0][j];
result += matrix[0][j];
}
for (i = 1; i < R; ++i)
{
for (j = 1; j < C; ++j)
{
if (matrix[i][j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i][j] = this->minimum(this->minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
}
else
{
auxiliary[i][j] = matrix[i][j];
}
result += auxiliary[i][j];
}
}
cout << "\n Total Square submatrix of 1's is : " << result << " \n";
}
};
int main()
{
// Define matrix of integer element which contains (0 and 1)
int matrix[R][C] = {
{
0 , 1 , 0 , 1 , 1 , 0
} , {
0 , 1 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
return 0;
}``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````// Include namespace system
using System;
/*
C# Program for
Count square submatrices with all ones
*/
public class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
public int minimum(int a, int b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
public void countSquareOnce(int[,] matrix)
{
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
// Auxiliary matrix which is used to find and store all square matrix
int[,] auxiliary = new int[row,col];
// Loop controllong variables
int i = 0;
int j = 0;
int result = 0;
// Set first element of each rows
for (i = 0; i < row; ++i)
{
auxiliary[i,0] = matrix[i,0];
result += matrix[i,0];
}
// Set first element of each columns
for (j = 0; j < col; ++j)
{
auxiliary[0,j] = matrix[0,j];
result += matrix[0,j];
}
for (i = 1; i < row; ++i)
{
for (j = 1; j < col; ++j)
{
if (matrix[i,j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i,j] = minimum(minimum(auxiliary[i,j - 1], auxiliary[i - 1,j - 1]), auxiliary[i - 1,j]) + 1;
}
else
{
auxiliary[i,j] = matrix[i,j];
}
result += auxiliary[i,j];
}
}
Console.Write("\n Total Square submatrix of 1's is : " + result + " \n");
}
public static void Main(String[] args)
{
// Define matrix of integer element which contains (0 and 1)
int[,] matrix = {
{
0 , 1 , 0 , 1 , 1 , 0
} , {
0 , 1 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
}
}``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````<?php
/*
Php Program for
Count square submatrices with all ones
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
public	function minimum(\$a, \$b)
{
if (\$a > \$b)
{
return \$b;
}
else
{
return \$a;
}
}
//count number of square submatrices with all 1s
public	function countSquareOnce( & \$matrix)
{
\$row = count(\$matrix);
\$col = count(\$matrix[0]);
// Auxiliary matrix which is used to find and store all square matrix
\$auxiliary = array_fill(0, \$row, array_fill(0, \$col, 0));
// Loop controllong variables
\$i = 0;
\$j = 0;
\$result = 0;
// Set first element of each rows
for (\$i = 0; \$i < \$row; ++\$i)
{
\$auxiliary[\$i][0] = \$matrix[\$i][0];
\$result += \$matrix[\$i][0];
}
// Set first element of each columns
for (\$j = 0; \$j < \$col; ++\$j)
{
\$auxiliary[0][\$j] = \$matrix[0][\$j];
\$result += \$matrix[0][\$j];
}
for (\$i = 1; \$i < \$row; ++\$i)
{
for (\$j = 1; \$j < \$col; ++\$j)
{
if (\$matrix[\$i][\$j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
\$auxiliary[\$i][\$j] = \$this->minimum(\$this->minimum(\$auxiliary[\$i][\$j - 1], \$auxiliary[\$i - 1][\$j - 1]), \$auxiliary[\$i - 1][\$j]) + 1;
}
else
{
\$auxiliary[\$i][\$j] = \$matrix[\$i][\$j];
}
\$result += \$auxiliary[\$i][\$j];
}
}
echo "\n Total Square submatrix of 1's is : ". \$result ." \n";
}
}

function main()
{
// Define matrix of integer element which contains (0 and 1)
\$matrix = array(
array(0, 1, 0, 1, 1, 0),
array(0, 1, 1, 1, 1, 1),
array(1, 1, 1, 1, 1, 1),
array(1, 0, 1, 1, 1, 1)
);
}
main();``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````/*
Node Js Program for
Count square submatrices with all ones
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
minimum(a, b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
countSquareOnce(matrix)
{
var row = matrix.length;
var col = matrix[0].length;
// Auxiliary matrix which is used to find and store all square matrix
var auxiliary = Array(row).fill(0).map(() => new Array(col).fill(0));
// Loop controllong variables
var i = 0;
var j = 0;
var result = 0;
// Set first element of each rows
for (i = 0; i < row; ++i)
{
auxiliary[i][0] = matrix[i][0];
result += matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < col; ++j)
{
auxiliary[0][j] = matrix[0][j];
result += matrix[0][j];
}
for (i = 1; i < row; ++i)
{
for (j = 1; j < col; ++j)
{
if (matrix[i][j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i][j] = this.minimum(this.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
}
else
{
auxiliary[i][j] = matrix[i][j];
}
result += auxiliary[i][j];
}
}
process.stdout.write("\n Total Square submatrix of 1's is : " + result + " \n");
}
}

function main()
{
// Define matrix of integer element which contains (0 and 1)
var matrix = [
[0, 1, 0, 1, 1, 0] ,
[0, 1, 1, 1, 1, 1] ,
[1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 1]
];
}
main();``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````#   Python 3 Program for
#   Count square submatrices with all ones

class SquareSubmatrix :
#  Returns the minimum value of given two numbers (integer)
def minimum(self, a, b) :
if (a > b) :
return b
else :
return a

# count number of square submatrices with all 1s
def countSquareOnce(self, matrix) :
row = len(matrix)
col = len(matrix[0])
#  Auxiliary matrix which is used to find and store all square matrix
auxiliary = [[0] * (col) for _ in range(row) ]
#  Loop controllong variables
i = 0
j = 0
result = 0
#  Set first element of each rows
while (i < row) :
auxiliary[i][0] = matrix[i][0]
result += matrix[i][0]
i += 1

#  Set first element of each columns
while (j < col) :
auxiliary[0][j] = matrix[0][j]
result += matrix[0][j]
j += 1

i = 1
while (i < row) :
j = 1
while (j < col) :
if (matrix[i][j] == 1) :
#
# Set x location value by minimum of side three elements (such as).
# x [this is current location]
# 	e2   e3
# 	  ╲   │
# 	   ╲  │
# 	    ╲ │
# 	e1‒‒‒ x

auxiliary[i][j] = self.minimum(self.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1
else :
auxiliary[i][j] = matrix[i][j]

result += auxiliary[i][j]
j += 1

i += 1

print("\n Total Square submatrix of 1's is : ", result ," ")

def main() :
#  Define matrix of integer element which contains (0 and 1)
matrix = [
[0, 1, 0, 1, 1, 0] ,
[0, 1, 1, 1, 1, 1] ,
[1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 1]
]

if __name__ == "__main__": main()``````

#### Output

`` Total Square submatrix of 1's is :  29``
``````#   Ruby Program for
#   Count square submatrices with all ones

class SquareSubmatrix
#  Returns the minimum value of given two numbers (integer)
def minimum(a, b)
if (a > b)
return b
else
return a
end

end

# count number of square submatrices with all 1s
def countSquareOnce(matrix)
row = matrix.length
col = matrix[0].length
#  Auxiliary matrix which is used to find and store all square matrix
auxiliary = Array.new(row) {Array.new(col) {0}}
#  Loop controllong variables
i = 0
j = 0
result = 0
#  Set first element of each rows
while (i < row)
auxiliary[i][0] = matrix[i][0]
result += matrix[i][0]
i += 1
end

#  Set first element of each columns
while (j < col)
auxiliary[0][j] = matrix[0][j]
result += matrix[0][j]
j += 1
end

i = 1
while (i < row)
j = 1
while (j < col)
if (matrix[i][j] == 1)
#
# Set x location value by minimum of side three elements (such as).
# x [this is current location]
# 	e2   e3
# 	  ╲   │
# 	   ╲  │
# 	    ╲ │
# 	e1‒‒‒ x

auxiliary[i][j] = self.minimum(self.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1
else
auxiliary[i][j] = matrix[i][j]
end

result += auxiliary[i][j]
j += 1
end

i += 1
end

print("\n Total Square submatrix of 1's is : ", result ," \n")
end

end

def main()
#  Define matrix of integer element which contains (0 and 1)
matrix = [
[0, 1, 0, 1, 1, 0] ,
[0, 1, 1, 1, 1, 1] ,
[1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 1]
]
end

main()``````

#### Output

`````` Total Square submatrix of 1's is : 29
``````
``````/*
Scala Program for
Count square submatrices with all ones
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
def minimum(a: Int, b: Int): Int = {
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
def countSquareOnce(matrix: Array[Array[Int]]): Unit = {
var row: Int = matrix.length;
var col: Int = matrix(0).length;
// Auxiliary matrix which is used to find and store all square matrix
var auxiliary: Array[Array[Int]] = Array.fill[Int](row, col)(0);
// Loop controllong variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 0;
// Set first element of each rows
while (i < row)
{
auxiliary(i)(0) = matrix(i)(0);
result += matrix(i)(0);
i += 1;
}
// Set first element of each columns
while (j < col)
{
auxiliary(0)(j) = matrix(0)(j);
result += matrix(0)(j);
j += 1;
}
i = 1;
while (i < row)
{
j = 1;
while (j < col)
{
if (matrix(i)(j) == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary(i)(j) = this.minimum(this.minimum(auxiliary(i)(j - 1), auxiliary(i - 1)(j - 1)), auxiliary(i - 1)(j)) + 1;
}
else
{
auxiliary(i)(j) = matrix(i)(j);
}
result += auxiliary(i)(j);
j += 1;
}
i += 1;
}
print("\n Total Square submatrix of 1's is : " + result + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SquareSubmatrix = new SquareSubmatrix();
// Define matrix of integer element which contains (0 and 1)
var matrix: Array[Array[Int]] = Array(
Array(0, 1, 0, 1, 1, 0),
Array(0, 1, 1, 1, 1, 1),
Array(1, 1, 1, 1, 1, 1),
Array(1, 0, 1, 1, 1, 1)
);
}
}``````

#### Output

`` Total Square submatrix of 1's is : 29``
``````/*
Swift 4 Program for
Count square submatrices with all ones
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
func minimum(_ a: Int, _ b: Int)->Int
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
func countSquareOnce(_ matrix: [
[Int]
])
{
let row: Int = matrix.count;
let col: Int = matrix[0].count;
// Auxiliary matrix which is used to find and store all square matrix
var auxiliary: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
// Loop controllong variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 0;
// Set first element of each rows
while (i < row)
{
auxiliary[i][0] = matrix[i][0];
result += matrix[i][0];
i += 1;
}
// Set first element of each columns
while (j < col)
{
auxiliary[0][j] = matrix[0][j];
result += matrix[0][j];
j += 1;
}
i = 1;
while (i < row)
{
j = 1;
while (j < col)
{
if (matrix[i][j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i][j] = self.minimum(self.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
}
else
{
auxiliary[i][j] = matrix[i][j];
}
result += auxiliary[i][j];
j += 1;
}
i += 1;
}
print("\n Total Square submatrix of 1's is : ", result ," ");
}
}
func main()
{
// Define matrix of integer element which contains (0 and 1)
let matrix: [[Int]] = [
[0, 1, 0, 1, 1, 0] ,
[0, 1, 1, 1, 1, 1] ,
[1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 1]
];
}
main();``````

#### Output

`` Total Square submatrix of 1's is :  29``
``````/*
Kotlin Program for
Count square submatrices with all ones
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
fun minimum(a: Int, b: Int): Int
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
//count number of square submatrices with all 1s
fun countSquareOnce(matrix: Array < Array < Int >> ): Unit
{
var row: Int = matrix.count();
var col: Int = matrix[0].count();
// Auxiliary matrix which count() used to find and store all square matrix
var auxiliary: Array < Array < Int >> = Array(row)
{
Array(col)
{
0
}
};
// Loop controllong variables
var i: Int = 0;
var j: Int = 0;
var result: Int = 0;
// Set first element of each rows
while (i < row)
{
auxiliary[i][0] = matrix[i][0];
result += matrix[i][0];
i += 1;
}
// Set first element of each columns
while (j < col)
{
auxiliary[0][j] = matrix[0][j];
result += matrix[0][j];
j += 1;
}
i = 1;
while (i < row)
{
j = 1;
while (j < col)
{
if (matrix[i][j] == 1)
{
/*
Set x location value by minimum of side three elements (such as).
x [this is current location]

e2   e3
╲   │
╲  │
╲ │
e1‒‒‒ x
*/
auxiliary[i][j] = this.minimum(this.minimum(auxiliary[i][j - 1], auxiliary[i - 1][j - 1]), auxiliary[i - 1][j]) + 1;
}
else
{
auxiliary[i][j] = matrix[i][j];
}
result += auxiliary[i][j];
j += 1;
}
i += 1;
}
print("\n Total Square submatrix of 1's is : " + result + " \n");
}
}
fun main(args: Array < String > ): Unit
{
// Define matrix of integer element which contains (0 and 1)
var matrix: Array <Array<Int>> = arrayOf(
arrayOf(0, 1, 0, 1, 1, 0),
arrayOf(0, 1, 1, 1, 1, 1),
arrayOf(1, 1, 1, 1, 1, 1),
arrayOf(1, 0, 1, 1, 1, 1)
);
}``````

#### Output

`` Total Square submatrix of 1's is : 29``

## Output Explanation

The given Java code implements the above algorithm to count the number of square submatrices with all ones in the given 2D matrix.

The output shows the total number of square submatrices with all ones in the input matrix, which is 29.

## Time Complexity

The time complexity of the provided solution is O(row * col), where 'row' is the number of rows and 'col' is the number of columns in the 2D matrix. The function traverses each element in the matrix once, and each operation takes constant time. Therefore, the overall time complexity is linear in the size of the matrix.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post