Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 2 2 0 1 2 2 3 1 0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
C++
// C++ code for Maximum size square // sub-matrix with all 1s #include <bits/stdc++.h> #define bool int #define R 6 #define C 5 using namespace std; void printMaxSubSquare(bool M[R][C]) { int i,j; int S[R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/ for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = min(S[i][j-1],min( S[i-1][j], S[i-1][j-1])) + 1; else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } cout<<"Maximum size sub-matrix is:
"; for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { cout << M[i][j] << " "; } cout << "
"; } } /* Driver code */int main() { bool M[R][C] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } // This is code is contributed by rathbhupendra |
C
// C code for Maximum size square // sub-matrix with all 1s #include<stdio.h> #define bool int #define R 6 #define C 5 void printMaxSubSquare(bool M[R][C]) { int i,j; int S[R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1; else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } printf("Maximum size sub-matrix is:
"); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { printf("%d ", M[i][j]); } printf("
"); } } /* UTILITY FUNCTIONS *//* Function to get minimum of three values */int min(int a, int b, int c) { int m = a; if (m > b) m = b; if (m > c) m = c; return m; } /* Driver function to test above functions */int main() { bool M[R][C] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); getchar(); } |
Java
// JAVA Code for Maximum size square // sub-matrix with all 1s public class GFG { // method for Maximum size square sub-matrix with all 1s static void printMaxSubSquare(int M[][]) { int i,j; int R = M.length; //no of rows in M[][] int C = M[0].length; //no of columns in M[][] int S[][] = new int[R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/ for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = Math.min(S[i][j-1], Math.min(S[i-1][j], S[i-1][j-1])) + 1; else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } System.out.println("Maximum size sub-matrix is: "); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { System.out.print(M[i][j] + " "); } System.out.println(); } } // Driver program public static void main(String[] args) { int M[][] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } } |
Python3
# Python3 code for Maximum size # square sub-matrix with all 1s def printMaxSubSquare(M): R = len(M) # no. of rows in M[][] C = len(M[0]) # no. of columns in M[][] S = [[0 for k in range(C)] for l in range(R)] # here we have set the first row and column of S[][] # Construct other entries for i in range(1, R): for j in range(1, C): if (M[i][j] == 1): S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 else: S[i][j] = 0 # Find the maximum entry and # indices of maximum entry in S[][] max_of_s = S[0][0] max_i = 0 max_j = 0 for i in range(R): for j in range(C): if (max_of_s < S[i][j]): max_of_s = S[i][j] max_i = i max_j = j print("Maximum size sub-matrix is: ") for i in range(max_i, max_i - max_of_s, -1): for j in range(max_j, max_j - max_of_s, -1): print (M[i][j], end = " ") print("") # Driver Program M = [[0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]] printMaxSubSquare(M) # This code is contributed by Soumen Ghosh |
C#
// C# Code for Maximum size square // sub-matrix with all 1s using System; public class GFG { // method for Maximum size square sub-matrix with all 1s static void printMaxSubSquare(int [,]M) { int i,j; //no of rows in M[,] int R = M.GetLength(0); //no of columns in M[,] int C = M.GetLength(1); int [,]S = new int[R,C]; int max_of_s, max_i, max_j; /* Set first column of S[,]*/ for(i = 0; i < R; i++) S[i,0] = M[i,0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0,j] = M[0,j]; /* Construct other entries of S[,]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i,j] == 1) S[i,j] = Math.Min(S[i,j-1], Math.Min(S[i-1,j], S[i-1,j-1])) + 1; else S[i,j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[,] */ max_of_s = S[0,0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i,j]) { max_of_s = S[i,j]; max_i = i; max_j = j; } } } Console.WriteLine("Maximum size sub-matrix is: "); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { Console.Write(M[i,j] + " "); } Console.WriteLine(); } } // Driver program public static void Main() { int [,]M = new int[6,5]{{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } } |
PHP
<?php // PHP code for Maximum size square // sub-matrix with all 1s function printMaxSubSquare($M, $R, $C) { $S = array(array()) ; /* Set first column of S[][]*/ for($i = 0; $i < $R; $i++) $S[$i][0] = $M[$i][0]; /* Set first row of S[][]*/ for($j = 0; $j < $C; $j++) $S[0][$j] = $M[0][$j]; /* Construct other entries of S[][]*/ for($i = 1; $i < $R; $i++) { for($j = 1; $j < $C; $j++) { if($M[$i][$j] == 1) $S[$i][$j] = min($S[$i][$j - 1], $S[$i - 1][$j], $S[$i - 1][$j - 1]) + 1; else $S[$i][$j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ $max_of_s = $S[0][0]; $max_i = 0; $max_j = 0; for($i = 0; $i < $R; $i++) { for($j = 0; $j < $C; $j++) { if($max_of_s < $S[$i][$j]) { $max_of_s = $S[$i][$j]; $max_i = $i; $max_j = $j; } } } printf("Maximum size sub-matrix is:
"); for($i = $max_i; $i > $max_i - $max_of_s; $i--) { for($j = $max_j; $j > $max_j - $max_of_s; $j--) { echo $M[$i][$j], " " ; } echo "
" ; } } # Driver code $M = array(array(0, 1, 1, 0, 1), array(1, 1, 0, 1, 0), array(0, 1, 1, 1, 0), array(1, 1, 1, 1, 0), array(1, 1, 1, 1, 1), array(0, 0, 0, 0, 0)); $R = 6 ; $C = 5 ; printMaxSubSquare($M, $R, $C); // This code is contributed by Ryuga ?> |
Output:
Maximum size sub-matrix is: 1 1 1 1 1 1 1 1 1
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Algorithmic Paradigm: Dynamic Programming
Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem
leave a comment
0 Comments