Maximum size square sub-matrices with all 1's

Posted in

Maximum size square sub-matrices with all 1's
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    Problem Statement

    Consider a matrix with all 0s and 1s. Your task is to find the largest square sub-matrix, which contains all 1s in it.

    Approach 1 - DP (Bottom Up)

    This approach is very simple, for every cell in the matrix , consider the cells which surround it.

    Example 1 In the below image, consider the left side matrix as arr1[][] and right side matrix as arr2[][].

    To find the value of arr2[1][1], we need to find the minimum value of the cells surrounded by it, i.e., arr1[0][0], arr1[0][1], and arr1[1][0]. The value of each cell is as follows: arr1[0][0] = 1, arr1[0][1] = 0, arr1[1][0] = 0 The minimum value is 0. Add 1 with the minimum of these values and write the result in the desired cell. So, arr2[1][1] = 1.

    Example 2

    We need to find the value of arr2[2][2], so we find the minimum value of the cells surrounded by it, i.e., arr1[1][1], arr1[1][2], and arr1[2][1]. The values of each cell is: arr1[1][1] = 1, arr1[1][2] = 1, arr1[2][1] = 0 The minimum value is again 0. So, we add the minimum value with 1 and write the result in the desired cell. So, arr2[1][2] = 1.

    Example 3

    We need to find the value of arr2[1][2], so we find the minimum value of the cells surrounded by it i.e. arr1[0][1], arr1[0][2], and arr1[1][1]. The values are arr1[0][1] = 2, arr1[0][2] = 2, arr1[1][1] = 1. The minimum value is 1 this time. So, we add the minimum value with 1 and write the result in the desired cell. So, arr2[1][2] = 2

    Example 4

    We need to find the value of arr2[4][6], so we find the minimum value of the cells surrounded by it i.e. arr1[3][4], arr1[3][5], and arr1[4][4]. The values are arr1[3][4] = 2 , arr1[3][5] = 2, and arr1[4][4] = 2. The minimum value is 2.

    So, we add the minimum value with 1 and write the result in the desired cell. So, arr2[4][6] = 3. We can follow the same approach mentioned in the above examples to find values for all the cells of a matrix. Following is an input matrix and its resultant matrix: Input matrix:

    Resultant matrix:

    Algorithm:

    1. Consider 2 arrays arr1[][] and arr2[][].
    2. Copy the given matrix into arr1[][].
    3. Now copy the first row and first column of arr1[][] to arr2[][].
    4. The below steps must be followed to copy the rest of the matrix:
      • If the value at arr1[][] == 0, simply copy that value to arr2[][] i.e. arr2[][] = 0.
      • If the value at arr1[][] == 1, then arr2[] = min_value(min(arr1[i-1][j-1],arr1[i][j-1],arr1[i-1][j])+1.

    We have used Dynamic Programming to solve the above approach.

    • C++ Code

    #include <bits/stdc++.h>
    #define bool int
    #define Row 7
    #define Column 6
    using namespace std;
    
    void MaxSubSquare(bool arr1[Row][Column])
    {
    	int i,j;
    	int arr2[Row][Column];
    	int max_arr2, max_of_i, max_of_j;
    	
    	//Copying first row of arr1 to arr2
    	for(j = 0; j < Column; j++)
    		arr2[0][j] = arr1[0][j];
    		
    	//Copying first column of arr1 to arr2
    	for(i = 0; i < Row; i++)
    		arr2[i][0] = arr1[i][0];
    		
    	//Other Matrix cells
    	i=1;
    	while(i<Row)
    	{
    		j=1;
    		while(j<Column)
    		{
    			if(arr1[i][j] == 1)
    				arr2[i][j] = min(arr2[i][j-1],min( arr2[i-1][j],arr2[i-1][j-1])) + 1;
    			else
    				arr2[i][j] = 0;	
    		j++;
    		}
    	i++;
    	}
    	
    	
    	//Finding Maximum entry
    	//Finding indexes of maximum entry from arr2
    	max_arr2 = arr2[0][0]; max_of_i = 0; max_of_j = 0;
    	for(i = 0; i < Row; i++)
    	{
    		for(j = 0; j < Column; j++)
    		{
    			if(max_arr2 < arr2[i][j])
    			{
    				max_arr2 = arr2[i][j];
    				max_of_i = i;
    				max_of_j = j;
    			}
    		}			
    	}
    
    	cout<<"Possible Maximum Sub Matrix is: \n"; for(i = max_of_i; i > max_of_i - max_arr2; i--)
    	{
    		for(j = max_of_j; j > max_of_j - max_arr2; j--)
    		{
    			cout << arr1[i][j] << " ";
    		}
    		cout << "\n";
    	}
    }
    
    
    // Driver code 
    int main()
    {
    	bool arr1[Row][Column] = 	{{1,0,0,0,1,1},
    								{0,1,1,1,1,0},
    								{1,1,1,1,1,1},
    								{0,1,1,1,1,0},
    								{0,1,1,1,1,0},
    								{1,1,0,1,1,0},
    								{0,0,1,1,0,0},
    							};
    					
    	MaxSubSquare(arr1);
    }

    Output:

    • Java Code

    public class Main
    {
        public static void MaxSubSquare(int arr1[][])
        {
            int i,j;
            int Row = arr1.length;       //no of rows in M[][]
            int Column = arr1[0].length;     //no of columns in M[][]
            int arr2[][] = new int[Row][Column];    
            
            int max_arr2, max_of_i, max_of_j;
        
            //Copying first column to arr2
            for(i = 0; i < Row; i++)
                arr2[i][0] = arr1[i][0];
        
            //Copying first row to arr2
            for(j = 0; j < Column; j++)
                arr2[0][j] = arr1[0][j];
            
            // Other Cells
            for(i = 1; i < Row; i++)
            {
                for(j = 1; j < Column; j++)
                {
                    if(arr1[i][j] == 1)
                    arr2[i][j] = Math.min(arr2[i][j-1],Math.min(arr2[i-1][j], arr2[i-1][j-1])) + 1;
                    else
                        arr2[i][j] = 0;
                }
            }   
            
            //Find Maximum entry
            //Finding indexes of maximum entry from arr2
            max_arr2 = arr2[0][0]; max_of_i = 0; max_of_j = 0;
            for(i = 0; i < Row; i++)
            {
                for(j = 0; j < Column; j++)
                {
                    if(max_arr2 < arr2[i][j]) { max_arr2 = arr2[i][j]; max_of_i = i; max_of_j = j; } } } System.out.println("Possible Maximum Sub Matrix is: "); for(i = max_of_i; i > max_of_i - max_arr2; i--)
            {
                for(j = max_of_j; j > max_of_j - max_arr2; j--)
                {
                    System.out.print(arr1[i][j] + " ");
                }
                System.out.println();
            }
        }
        
        // Driver program
        public static void main(String[] args)
        {
            int arr1[][] = {{0,1,1,1,1,0},
                                    {1,1,1,1,1,1},
                                    {0,1,1,1,1,0},
                                    {0,1,1,1,1,0},
                                    {1,1,0,1,1,0},
                                    {0,0,1,1,0,0},};
                
            MaxSubSquare(arr1);
        }
    }

    Output:

    • Python Code

    def MaxSubSquare(M):
        R = len(arr1) 
        C = len(arr1[0]) 
    
        S = [[0 for k in range(C)] for l in range(R)]
        # Copying first row & columnto arr2
    
        # Other Cells
        for i in range(1, R):
            for j in range(1, C):
                if (arr1[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
        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 (arr1[i][j], end = " ")
            print("")
    
    # Driver Program
    arr1 = [[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]]
    
    MaxSubSquare(arr1)

    Output:

    Complexity Analysis

    Time Complexity : O(m*n). This is so because we have to traverse the entire matrix of size m*n. Space Complexity : O(m*n). This is so because we have to store the matrix.

    Approach 2 - DP (Top Down)

    Consider a matrix with all 0s and 1s. The task is to find the largest square submatrix which would be the largest matrix, and this submatrix should contain all 1s. To understand this approach for finding the maximum size square sub-matrices, let us consider the below matrix to explain the DP (top-down) approach:

    The top-left corner should at least have size (n-1)x(n-1) so that an (n x n) sub-matrix can be formed.

    Algorithm:

    1. Initialize the matrix with values.
    2. Call the SubSquare function with suitable parameters.
    3. Find the largest square matrix at every row and store it in a variable.
    4. Find the largest square matrix at every column and store it in a variable.
    5. Now, print the largest value of the square sub-matrix.
    • Python Code

    def SubSquare(arr1, row, column, max_value):
        # Termination condition
        if row == 0 or column == 0:.
    
     
            if max_value != 0:
                return arr1[row][column], max(max_value, arr1[row][column])
     
            for i in range(row+1):
                    if arr1[i][column] == 1:
                        return 1, 1
     
            for j in range(column+1):
                    if arr1[row][j] == 1:
                        return 1, 1
     
            return 0, 0
     
        #finding largestsquare matrix at the specific row
        l, max_value = SubSquare(arr1,row,column-1,max_value)
     
        #finding largestsquare matrix at the specific column
        t, max_value = SubSquare(arr1,row-1,column,max_value)
     
        # Finding largest value of square matrix 
        diagonal, max_value = SubSquare(arr1,row-1,column-1,max_value)
        
        size = 1 + min(min(t,l),diagonal) if arr1[row][column] else 0
     
        
        return size, max(max_value, size)
    if __name__ == '__main__':
        arr1 = [
               [0,1,1,1,1,0],
               [1,1,1,1,1,1],
               [0,1,1,1,1,0],
               [0,1,1,1,1,0],
               [1,1,0,1,1,0],
               [1,1,0,1,1,0],
            ]
     
        max_value = SubSquare(arr1, len(arr1) - 1, len(arr1[0]) - 1, 0)[1]
        print("Size of largest square submatrix :", max_value)

    Output:

    • Java Code

    import java.util.concurrent.atomic.AtomicInteger;
    class Main
    {
        //Finding size of largest square sub matrix
        public static int SubSquare(int[][] arr1, int row, int column, AtomicInteger max_size)
        {
            int i,j;
            // termination condition
            if (row==0||column==0)
            {
                if (max_size.get() != 0)
                {
                    max_size.set(Integer.max(max_size.get(), arr1[row][column]));
                    return arr1[row][column];
                }
                for(i=0;i<=row;i++)
                {
                    if(arr1[i][column] == 1)
                    {
                        max_size.set(1);
                        break;
                    }
                }
                for (j = 0; j <= column; j++)
                {
                    if (arr1[row][j] == 1)
                    {
                        max_size.set(1);
                        break;
                    }
                }
                return max_size.get();
            }
     
    
            //Finding largest square matrix at ROW
            int l = SubSquare(arr1,row,column-1,max_size);
     
            //Finding largest square matrix at column
            int t = SubSquare(arr1,row-1,column,max_size);
     
            //Finding largest square matrix in Matrix 
            int d = SubSquare(arr1,row-1,column-1,max_size);
     
            //1+min(three values of largest square matrix)
     
            int size = 0;
            if (arr1[row][column] != 0) {
                size = 1 + Integer.min(Integer.min(t,l),d);
            }
     
            // Maximum size
            max_size.set(Integer.max(max_size.get(), size));
     
            return size;
        }
     
        public static void main(String[] args)
        {
            int[][] arr1 =
            {
                                    {0,1,1,1,1,0},
                                    {1,1,1,1,1,1},
                                    {0,1,1,1,1,0},
                                    {0,1,1,1,1,0},
                                    {1,1,0,1,1,0},
                                    {0,0,1,1,0,0},
            };
            AtomicInteger max_size = new AtomicInteger();
            SubSquare(arr1,arr1.length-1,arr1[0].length-1,max_size);
            System.out.print("Size of largest square submatrix :" +max_size.get());
        }
    }

    Output:

    • C++ code

    #include <iostream>
    using namespace std;
    
    #define row 6
    #define column 7
    int SubSquare(int arr1[row][column], int m, int n, int &max_size)
    {
        int l,t,tl;
        // base condition
        if (m==0 || n==0)
        {
            if(max_size != 0)
            {
                max_size = max(max_size, arr1[m][n]);
                return arr1[m][n];
            }
     
            for (int i = 0; i <= m; i++)
            {
                if (arr1[i][n] == 1)
                {
                    max_size = 1;
                    break;
                }
            }
     
            for (int j = 0; j <= n; j++)
            {
                if (arr1[m][j] == 1)
                {
                    max_size = 1;
                    break;
                }
            }
     
            return max_size;
        }
     
        // Finding largest square matrix at row
        l = SubSquare(arr1, m, n - 1, max_size);
     
        // Finding largest square matrix at column
        t = SubSquare(arr1, m - 1, n, max_size);
     
        // Finding largest square matrix of matrix
        tl = SubSquare(arr1, m - 1, n - 1, max_size);
     
                // Maximum size
                //max_size.set(Integer.max(max_size.get(), size))
        int size = 0;
        if (arr1[m][n] != 0) {
            size = 1 + min (min(t, l), tl);
        }
     
        max_size = max(max_size, size);
    
        return size;
    }
     
    int main()
    {
        int arr1[row][column] =
        {
                                    {0,1,1,1,1,0},
                                    {1,1,1,1,1,1},
                                    {0,1,1,1,1,0},
                                    {0,1,1,1,1,0},
                                    {1,1,0,1,1,0},
                                    {0,0,1,1,0,0},
        };
         int size = 0;
        
        SubSquare(arr1, row - 1, column - 1, size);
     
        cout << "Size of largest square sub matrix is: " << size;
     
        return 0;
    }

    Output:

    Conclusion

    In this tutorial, we have discussed the problem “Maximum size square submatrix with all 1s” with an in-depth explanation of its solution. We started with a general introduction of the problem statement with an example and then we discussed two dynamic programming approaches to solve the problem.

    We certainly hope that by going through this article, you will be able to understand how to solve the problem of maximum size square sub-matrices with all 1s with ease.

    People are also reading:

    Leave a Comment on this Post

    0 Comments