# Maximum size square sub-matrix with all 1s

Here given code implementation process.

``````// C Program
// Maximum size square sub-matrix with all 1s
#include <stdio.h>

// Matrix size
#define R 12
#define C 10
// Returns the minimum value of given two numbers (integer)
int minimum(int a, int b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
void maximumSquare(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;
// This is used to detect square matrix location
int a = -1;
int b = -1;
// Set first element of each rows
for (i = 0; i < R; ++i)
{
auxiliary[i][0] = matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < C; ++j)
{
auxiliary[0][j] = matrix[0][j];
}
for (i = 1; i < R; ++i)
{
for (j = 1; j < C; ++j)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
}
}
if (a == -1 && b == -1)
{
printf("\n None ");
}
else
{
// Get top left location
i = a - (auxiliary[a][b] - 1);
j = b - (auxiliary[a][b] - 1);
// Display location of sub matrix
printf("  Maximum Submatrix exists at location (%d,%d) (%d,%d) ", i, j, a, b);
printf("\n  Maximum size : %d \n", auxiliary[a][b]);
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
printf("  %d", matrix[i][j]);
j++;
}
printf("\n");
// next row
i++;
// Get first resultant column
j = b - (auxiliary[a][b] - 1);
}
}
printf("\n");
}
int main(int argc, char
const *argv[])
{
// Define matrix of integer element which contains (0 and 1)
int matrix[R][C] =
{
{0, 1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 0, 0, 0, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{0, 0, 0, 1, 1, 1, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 1, 0, 1, 1, 0, 1}
};
maximumSquare(matrix);
return 0;
}``````

#### Output

``````  Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1  1  1  1
1  1  1  1
1  1  1  1
1  1  1  1
``````
``````/*
Java Program for
Maximum size square sub-matrix with all 1s
*/
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;
}
}

// Finding the Maximum size rectangle binary sub-matrix with all 1s
public void maximumSquare(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;
// This is used to detect square matrix location
int a = -1;
int b = -1;
// Set first element of each rows
for (i = 0; i < row; ++i)
{
auxiliary[i][0] = matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < col; ++j)
{
auxiliary[0][j] = matrix[0][j];
}
for (i = 1; i < row; ++i)
{
for (j = 1; j < col; ++j)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
}
}
if (a == -1 && b == -1)
{
System.out.print("\n None ");
}
else
{
// Get top left location
i = a - (auxiliary[a][b] - 1);
j = b - (auxiliary[a][b] - 1);
// Display location of sub matrix
System.out.print(" Maximum Submatrix exists at location (" + i + "," + j + ") (" + a + "," + b + ") ");
System.out.print("\n Maximum size : " + auxiliary[a][b] + " \n");
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
System.out.print(" " + matrix[i][j] + "");
j++;
}
System.out.print("\n");
// next row
i++;
// Get first resultant column
j = b - (auxiliary[a][b] - 1);
}
}
System.out.print("\n");
}

public static void main(String[] args)
{
// Define matrix of integer element which contains (0 and 1)
int[][] matrix =
{
{0, 1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 0, 0, 0, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{0, 0, 0, 1, 1, 1, 1, 0, 0, 1},
{1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 1, 0, 1, 1, 0, 1}
};
}
}``````

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````
``````// Include header file
#include <iostream>
// Matrix size
#define R 12
#define C 10
using namespace std;
/*
C++ Program for
Maximum size square sub-matrix with all 1s
*/
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;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
void maximumSquare(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;
// This is used to detect square matrix location
int a = -1;
int b = -1;
// Set first element of each rows
for (i = 0; i < R; ++i)
{
auxiliary[i][0] = matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < C; ++j)
{
auxiliary[0][j] = matrix[0][j];
}
for (i = 1; i < R; ++i)
{
for (j = 1; j < C; ++j)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
}
}
if (a == -1 && b == -1)
{
cout << "\n None ";
}
else
{
// Get top left location
i = a - (auxiliary[a][b] - 1);
j = b - (auxiliary[a][b] - 1);
// Display location of sub matrix
cout << " Maximum Submatrix exists at location (" << i << "," << j << ") (" << a << "," << b << ") ";
cout << "\n Maximum size : " << auxiliary[a][b] << " \n";
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
cout << " " << matrix[i][j] << "";
j++;
}
cout << "\n";
// next row
i++;
// Get first resultant column
j = b - (auxiliary[a][b] - 1);
}
}
cout << "\n";
}
};
int main()
{
// Define matrix of integer element which contains (0 and 1)
int matrix[R][C] =
{
{0, 1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 0, 0, 0, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{0, 0, 0, 1, 1, 1, 1, 0, 0, 1},
{1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 1, 0, 1, 1, 0, 1}
};
return 0;
}``````

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````
``````// Include namespace system
using System;
/*
C# Program for
Maximum size square sub-matrix with all 1s
*/
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;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
public void maximumSquare(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;
// This is used to detect square matrix location
int a = -1;
int b = -1;
// Set first element of each rows
for (i = 0; i < row; ++i)
{
auxiliary[i,0] = matrix[i,0];
}
// Set first element of each columns
for (j = 0; j < col; ++j)
{
auxiliary[0,j] = matrix[0,j];
}
for (i = 1; i < row; ++i)
{
for (j = 1; j < col; ++j)
{
// Set the initial element of matrix auxiliary [i,j] as zero
auxiliary[i,j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i,j] > auxiliary[a,b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
}
}
if (a == -1 && b == -1)
{
Console.Write("\n None ");
}
else
{
// Get top left location
i = a - (auxiliary[a,b] - 1);
j = b - (auxiliary[a,b] - 1);
// Display location of sub matrix
Console.Write(" Maximum Submatrix exists at location (" + i + "," + j + ") (" + a + "," + b + ") ");
Console.Write("\n Maximum size : " + auxiliary[a,b] + " \n");
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
Console.Write(" " + matrix[i,j] + "");
j++;
}
Console.Write("\n");
// next row
i++;
// Get first resultant column
j = b - (auxiliary[a,b] - 1);
}
}
Console.Write("\n");
}
public static void Main(String[] args)
{
// Define matrix of integer element which contains (0 and 1)
int[,] matrix = {
{
0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 1
} , {
0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1
} , {
1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1
} , {
1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 1
} , {
0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1
}
};
}
}``````

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````
``````<?php
/*
Php Program for
Maximum size square sub-matrix with all 1s
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
public	function minimum(\$a, \$b)
{
if (\$a > \$b)
{
return \$b;
}
else
{
return \$a;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
public	function maximumSquare( \$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;
// This is used to detect square matrix location
\$a = -1;
\$b = -1;
// Set first element of each rows
for (\$i = 0; \$i < \$row; ++\$i)
{
\$auxiliary[\$i][0] = \$matrix[\$i][0];
}
// Set first element of each columns
for (\$j = 0; \$j < \$col; ++\$j)
{
\$auxiliary[0][\$j] = \$matrix[0][\$j];
}
for (\$i = 1; \$i < \$row; ++\$i)
{
for (\$j = 1; \$j < \$col; ++\$j)
{
// Set the initial element of matrix auxiliary [i][j] as zero
\$auxiliary[\$i][\$j] = 0;
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;
if ((\$a == -1 && \$b == -1) || (\$auxiliary[\$i][\$j] > \$auxiliary[\$a][\$b]))
{
// When getting the new higher square matrix
\$a = \$i;
\$b = \$j;
}
}
}
}
if (\$a == -1 && \$b == -1)
{
echo "\n None ";
}
else
{
// Get top left location
\$i = \$a - (\$auxiliary[\$a][\$b] - 1);
\$j = \$b - (\$auxiliary[\$a][\$b] - 1);
// Display location of sub matrix
echo " Maximum Submatrix exists at location (". \$i .",". \$j .") (". \$a .",". \$b .") ";
echo "\n Maximum size : ". \$auxiliary[\$a][\$b] ." \n";
// Display result
// Rows
while (\$i <= \$a)
{
// Columns
while (\$j <= \$b)
{
echo " ". \$matrix[\$i][\$j] ."";
\$j++;
}
echo "\n";
// next row
\$i++;
// Get first resultant column
\$j = \$b - (\$auxiliary[\$a][\$b] - 1);
}
}
echo "\n";
}
}

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

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````
``````/*
Node Js Program for
Maximum size square sub-matrix with all 1s
*/
class SquareSubmatrix
{
// Returns the minimum value of given two numbers (integer)
minimum(a, b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
maximumSquare(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;
// This is used to detect square matrix location
var a = -1;
var b = -1;
// Set first element of each rows
for (i = 0; i < row; ++i)
{
auxiliary[i][0] = matrix[i][0];
}
// Set first element of each columns
for (j = 0; j < col; ++j)
{
auxiliary[0][j] = matrix[0][j];
}
for (i = 1; i < row; ++i)
{
for (j = 1; j < col; ++j)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
}
}
if (a == -1 && b == -1)
{
process.stdout.write("\n None ");
}
else
{
// Get top left location
i = a - (auxiliary[a][b] - 1);
j = b - (auxiliary[a][b] - 1);
// Display location of sub matrix
process.stdout.write(" Maximum Submatrix exists at location (" + i + "," + j + ") (" + a + "," + b + ") ");
process.stdout.write("\n Maximum size : " + auxiliary[a][b] + " \n");
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
process.stdout.write(" " + matrix[i][j] + "");
j++;
}
process.stdout.write("\n");
// next row
i++;
// Get first resultant column
j = b - (auxiliary[a][b] - 1);
}
}
process.stdout.write("\n");
}
}

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

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````
``````#   Python 3 Program for
#   Maximum size square sub-matrix with all 1s

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

#  Finding the Maximum size rectangle binary sub-matrix with all 1s
def maximumSquare(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
#  This is used to detect square matrix location
a = -1
b = -1
#  Set first element of each rows
while (i < row) :
auxiliary[i][0] = matrix[i][0]
i += 1

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

i = 1
while (i < row) :
j = 1
while (j < col) :
#  Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0
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
if ((a == -1 and b == -1) or(auxiliary[i][j] > auxiliary[a][b])) :
#  When getting the new higher square matrix
a = i
b = j

j += 1

i += 1

if (a == -1 and b == -1) :
print("\n None ", end = "")
else :
#  Get top left location
i = a - (auxiliary[a][b] - 1)
j = b - (auxiliary[a][b] - 1)
#  Display location of sub matrix
print(" Maximum Submatrix exists at location (", i ,",", j ,") (", a ,",", b ,") ", end = "")
print("\n Maximum size : ", auxiliary[a][b] ," ")
#  Display result
#  Rows
while (i <= a) :
#  Columns
while (j <= b) :
print(" ", matrix[i][j] ,"", end = "")
j += 1

print(end = "\n")
#  next row
i += 1
#  Get first resultant column
j = b - (auxiliary[a][b] - 1)

print(end = "\n")

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

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

#### Output

`````` Maximum Submatrix exists at location ( 4 , 3 ) ( 7 , 6 )
Maximum size :  4
1   1   1   1
1   1   1   1
1   1   1   1
1   1   1   1
``````
``````#   Ruby Program for
#   Maximum size square sub-matrix with all 1s

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

#  Finding the Maximum size rectangle binary sub-matrix with all 1s
def maximumSquare(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
#  This is used to detect square matrix location
a = -1
b = -1
#  Set first element of each rows
while (i < row)
auxiliary[i][0] = matrix[i][0]
i += 1
end

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

i = 1
while (i < row)
j = 1
while (j < col)
#  Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0
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
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
#  When getting the new higher square matrix
a = i
b = j
end

end

j += 1
end

i += 1
end

if (a == -1 && b == -1)
print("\n None ")
else
#  Get top left location
i = a - (auxiliary[a][b] - 1)
j = b - (auxiliary[a][b] - 1)
#  Display location of sub matrix
print(" Maximum Submatrix exists at location (", i ,",", j ,") (", a ,",", b ,") ")
print("\n Maximum size : ", auxiliary[a][b] ," \n")
#  Display result
#  Rows
while (i <= a)
#  Columns
while (j <= b)
print(" ", matrix[i][j] ,"")
j += 1
end

print("\n")
#  next row
i += 1
#  Get first resultant column
j = b - (auxiliary[a][b] - 1)
end

end

print("\n")
end

end

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

main()``````

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

``````
``````/*
Scala Program for
Maximum size square sub-matrix with all 1s
*/
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;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
def maximumSquare(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;
// This is used to detect square matrix location
var a: Int = -1;
var b: Int = -1;
// Set first element of each rows
while (i < row)
{
auxiliary(i)(0) = matrix(i)(0);
i += 1;
}
// Set first element of each columns
while (j < col)
{
auxiliary(0)(j) = matrix(0)(j);
j += 1;
}
i = 1;
while (i < row)
{
j = 1;
while (j < col)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary(i)(j) = 0;
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;
if ((a == -1 && b == -1) || (auxiliary(i)(j) > auxiliary(a)(b)))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
j += 1;
}
i += 1;
}
if (a == -1 && b == -1)
{
print("\n None ");
}
else
{
// Get top left location
i = a - (auxiliary(a)(b) - 1);
j = b - (auxiliary(a)(b) - 1);
// Display location of sub matrix
print(" Maximum Submatrix exists at location (" + i + "," + j + ") (" + a + "," + b + ") ");
print("\n Maximum size : " + auxiliary(a)(b) + " \n");
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
print(" " + matrix(i)(j) + "");
j += 1;
}
print("\n");
// next row
i += 1;
// Get first resultant column
j = b - (auxiliary(a)(b) - 1);
}
}
print("\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, 1, 1, 1, 0, 1, 1, 0, 1),
Array(1, 1, 1, 0, 0, 0, 1, 1, 1, 1),
Array(1, 1, 1, 1, 1, 0, 1, 1, 0, 1),
Array(1, 1, 1, 1, 0, 0, 1, 0, 0, 1),
Array(0, 1, 1, 1, 1, 1, 1, 1, 0, 1),
Array(0, 0, 0, 1, 1, 1, 1, 0, 0, 1),
Array(1, 1, 0, 1, 1, 1, 1, 1, 0, 1),
Array(0, 1, 1, 1, 1, 1, 1, 1, 0, 1),
Array(1, 1, 1, 1, 0, 0, 0, 1, 0, 1),
Array(0, 1, 1, 1, 1, 0, 1, 1, 0, 1)
);
}
}``````

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````
``````/*
Swift 4 Program for
Maximum size square sub-matrix with all 1s
*/
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;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
func maximumSquare(_ 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;
// This is used to detect square matrix location
var a: Int = -1;
var b: Int = -1;
// Set first element of each rows
while (i < row)
{
auxiliary[i][0] = matrix[i][0];
i += 1;
}
// Set first element of each columns
while (j < col)
{
auxiliary[0][j] = matrix[0][j];
j += 1;
}
i = 1;
while (i < row)
{
j = 1;
while (j < col)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
j += 1;
}
i += 1;
}
if (a == -1 && b == -1)
{
print("\n None ", terminator: "");
}
else
{
// Get top left location
i = a - (auxiliary[a][b] - 1);
j = b - (auxiliary[a][b] - 1);
// Display location of sub matrix
print(" Maximum Submatrix exists at location (", i ,",", j ,") (", a ,",", b ,") ", terminator: "");
print("\n Maximum size : ", auxiliary[a][b] ," ");
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
print(" ", matrix[i][j] ,"", terminator: "");
j += 1;
}
print(terminator: "\n");
// next row
i += 1;
// Get first resultant column
j = b - (auxiliary[a][b] - 1);
}
}
print(terminator: "\n");
}
}
func main()
{
// Define matrix of integer element which contains (0 and 1)
let matrix: [[Int]] = [
[0, 1, 1, 1, 1, 0, 1, 1, 0, 1] ,
[1, 1, 1, 0, 0, 0, 1, 1, 1, 1] ,
[1, 1, 1, 1, 1, 0, 1, 1, 0, 1] ,
[1, 1, 1, 1, 0, 0, 1, 0, 0, 1] ,
[0, 1, 1, 1, 1, 1, 1, 1, 0, 1] ,
[0, 0, 0, 1, 1, 1, 1, 0, 0, 1] ,
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1] ,
[0, 1, 1, 1, 1, 1, 1, 1, 0, 1] ,
[1, 1, 1, 1, 0, 0, 0, 1, 0, 1] ,
[0, 1, 1, 1, 1, 0, 1, 1, 0, 1]
];
}
main();``````

#### Output

`````` Maximum Submatrix exists at location ( 4 , 3 ) ( 7 , 6 )
Maximum size :  4
1   1   1   1
1   1   1   1
1   1   1   1
1   1   1   1
``````
``````/*
Kotlin Program for
Maximum size square sub-matrix with all 1s
*/
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;
}
}
// Finding the Maximum size rectangle binary sub-matrix with all 1s
fun maximumSquare(matrix: Array<Array<Int>> ): Unit
{
var row: Int = matrix.count();
var col: Int = matrix[0].count();
// Auxiliary matrix which is 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;
// This is used to detect square matrix location
var a: Int = -1;
var b: Int = -1;
// Set first element of each rows
while (i < row)
{
auxiliary[i][0] = matrix[i][0];
i += 1;
}
// Set first element of each columns
while (j < col)
{
auxiliary[0][j] = matrix[0][j];
j += 1;
}
i = 1;
while (i < row)
{
j = 1;
while (j < col)
{
// Set the initial element of matrix auxiliary [i][j] as zero
auxiliary[i][j] = 0;
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;
if ((a == -1 && b == -1) || (auxiliary[i][j] > auxiliary[a][b]))
{
// When getting the new higher square matrix
a = i;
b = j;
}
}
j += 1;
}
i += 1;
}
if (a == -1 && b == -1)
{
print("\n None ");
}
else
{
// Get top left location
i = a - (auxiliary[a][b] - 1);
j = b - (auxiliary[a][b] - 1);
// Display location of sub matrix
print(" Maximum Submatrix exists at location (" + i + "," + j + ") (" + a + "," + b + ") ");
print("\n Maximum size : " + auxiliary[a][b] + " \n");
// Display result
// Rows
while (i <= a)
{
// Columns
while (j <= b)
{
print(" " + matrix[i][j] + "");
j += 1;
}
print("\n");
// next row
i += 1;
// Get first resultant column
j = b - (auxiliary[a][b] - 1);
}
}
print("\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, 1, 1, 1, 0, 1, 1, 0, 1),
arrayOf(1, 1, 1, 0, 0, 0, 1, 1, 1, 1),
arrayOf(1, 1, 1, 1, 1, 0, 1, 1, 0, 1),
arrayOf(1, 1, 1, 1, 0, 0, 1, 0, 0, 1),
arrayOf(0, 1, 1, 1, 1, 1, 1, 1, 0, 1),
arrayOf(0, 0, 0, 1, 1, 1, 1, 0, 0, 1),
arrayOf(1, 1, 0, 1, 1, 1, 1, 1, 0, 1),
arrayOf(0, 1, 1, 1, 1, 1, 1, 1, 0, 1),
arrayOf(1, 1, 1, 1, 0, 0, 0, 1, 0, 1),
arrayOf(0, 1, 1, 1, 1, 0, 1, 1, 0, 1)
);
}``````

#### Output

`````` Maximum Submatrix exists at location (4,3) (7,6)
Maximum size : 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
``````

## 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.