Posted on by Kalkicode
Code Matrix

Maximum size square sub-matrix with all 1s

The problem is to find the maximum size square sub-matrix with all ones in a given 2D matrix. A square sub-matrix is a contiguous sub-matrix where all the elements are ones.

Example

Consider the following 2D 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

The maximum size square sub-matrix with all ones in this matrix is:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Idea to Solve the Problem

To find the maximum size square sub-matrix 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 sub-matrix 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.
  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 sub-matrix with all ones that ends at the current cell.
  4. Find the maximum value in the auxiliary matrix. The value of this cell (i, j) represents the size of the maximum square sub-matrix with all ones. The top-left corner of this sub-matrix will be at the location (i - (value - 1), j - (value - 1)).

Pseudocode

maximumSquare(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
    a = -1, b = -1
    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
            set a = i and b = j
    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
                if auxiliary[i][j] > auxiliary[a][b]:
                    set a = i and b = j
    if a == -1 and b == -1:
        print "None" (no square sub-matrix with all ones)
    else:
        print "Maximum Submatrix exists at location (" + (a - (auxiliary[a][b] - 1)) + "," + (b - (auxiliary[a][b] - 1)) + ") (" + a + "," + b + ")"
        print "Maximum size : " + auxiliary[a][b]
        Print the sub-matrix starting from (a - (auxiliary[a][b] - 1), b - (auxiliary[a][b] - 1)) to (a, b) in the input matrix

Code Solution

// 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)
    {
        SquareSubmatrix task = new SquareSubmatrix();
        // 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}
        }; 
        task.maximumSquare(matrix);
    }
}

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()
{
    SquareSubmatrix task = SquareSubmatrix();
    // 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}
    }; 
    task.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
// 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)
	{
		SquareSubmatrix task = new SquareSubmatrix();
		// 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
			}
		};
		task.maximumSquare(matrix);
	}
}

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()
{
	$task = new SquareSubmatrix();
	// 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)
    );
	$task->maximumSquare($matrix);
}
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()
{
	var task = new SquareSubmatrix();
	// 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]
	];
	task.maximumSquare(matrix);
}
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() :
	task = SquareSubmatrix()
	#  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]
	]
	task.maximumSquare(matrix)

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() 
	task = SquareSubmatrix.new()
	#  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]
	]
	task.maximumSquare(matrix)
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)
        );
		task.maximumSquare(matrix);
	}
}

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()
{
	let task: SquareSubmatrix = SquareSubmatrix();
	// 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]
	];
	task.maximumSquare(matrix);
}
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
{
	var task: SquareSubmatrix = SquareSubmatrix();
	// 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)
    );
	task.maximumSquare(matrix);
}

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

Output Explanation

The java code implements the above algorithm to find the maximum size square sub-matrix with all ones in the given 2D matrix.

The output shows the location of the maximum square sub-matrix with all ones and its size. It also displays the sub-matrix.

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.

New Comment