Java Program to Find the Maximum Square Matrix with All 1’s

This is the Java Program to Find the Largest Square Matrix with all 1’s.

Problem Description

Given a boolean matrix of 0’s and 1’s, find and print the largest square sub-matrix whose all the entries are 1.
Example:
Matrix:
0 0 1 1
0 1 1 1
0 0 0 1

Output:
1 1
1 1

Problem Solution

Create a new matrix, say L of the same size. Initialize the first row and column of this new matrix with the first row and column of the original matrix. The values in this matrix represent the largest square sub-matrix whose all the entries are 1 that is present up to the indexes lets say, i and j. Traverse through the original matrix, if its entry is 1,that is M[i][j] = 1, then L[i][j] = min(L[i][j-1],L[i-1][j],L[i-1][j-1]) + 1, otherwise L[i][j] = 0. Find out the maximum value in matrix L and using it print the largest square sub-matrix.

Program/Source Code

Here is the source code of the Java Program to Find the Largest Square Matrix with all 1’s. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

```
 
```

//Java Program to Find the Largest Square Matrix with all 1's

```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
 
```
```
public class Max1SquareMatrix {
```

    // Function to find the largest square submatrix and display it.

    static void printSquareSubMatrix(int[][] matrix){

```
        int m,n;
```
```
        n=matrix.length;
```
```
        m=matrix[0].length;
```
```
        int[][] L = new int[n][m];
```
```
        int i,j;
```
```
        for(i=0; i<m; i++){
```
```
            L[0][i] = matrix[0][i];
```
```
        }
```
```
        for(i=0; i<n; i++){
```
```
            L[i][0] = matrix[i][0];
```
```
        }
```
```
        i=1;
```
```
        while(i<n){
```
```
            j=1;
```
```
            while(j<m){
```
```
                if(matrix[i][j] == 1){
```

                    L[i][j] = Math.min(L[i][j-1],

                                       Math.min(L[i-1][j-1],L[i-1][j]))+1;

```
                }
```
```
                else{
```
```
                    L[i][j] = 0;
```
```
                }
```
```
                j++;
```
```
            }
```
```
            i++;
```
```
        }
```
```
        int max = L[0][0];
```
```
        int max_i,max_j;
```
```
        max_i=max_j=0;
```
```
        i=0;
```
```
        while(i<n){
```
```
            j=0;
```
```
            while(j<m){
```
```
                if(L[i][j] > max){
```
```
                    max = L[i][j];
```
```
                    max_i = i;
```
```
                    max_j = j;
```
```
                }
```
```
                j++;
```
```
            }
```
```
            i++;
```
```
        }
```

        System.out.println("Maximum Sub-matrix");

```
        i = max_i;
```
```
        while(i>(max_i-max)){
```
```
            j = max_j;
```
```
            while(j>(max_j-max)){
```

                System.out.print(matrix[i][j]);

```
                j--;
```
```
            }
```
```
            System.out.println();
```
```
            i--;
```
```
        }
```
```
    }
```
```
    // Function to read user input
```

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int rows,columns;
```
```
        try{
```

            System.out.println("Enter the number of rows");

            rows = Integer.parseInt(br.readLine());

            System.out.println("Enter the number of columns");

            columns = Integer.parseInt(br.readLine());

```
        }
```
```
        catch(Exception e){
```

            System.out.println("An error occurred");

```
            return;
```
```
        }
```

        int[][] matrix = new int[rows][columns];

```
        int i,j;
```

        System.out.println("Enter the Boolean Matrix");

```
        try{
```
```
            for(i=0; i<rows; i++){
```

                for(j=0; j<columns; j++){

                    matrix[i][j] = Integer.parseInt(br.readLine());

```
                }
```
```
            }
```
```
        }catch (Exception e){
```

            System.out.println("An error occurred");

```
            return;
```
```
        }
```

        System.out.println("The matrix is");

```
        for(i=0; i<rows; i++){
```
```
            for(j=0; j<columns; j++){
```

                System.out.print(matrix[i][j]);

```
            }
```
```
            System.out.println();
```
```
        }
```
```
        if(rows > 0 && columns > 0)
```

            printSquareSubMatrix(matrix);

```
    }
```
```
}
```

Program Explanation

1. In function printSquareSubMatrix(), a new matrix L is created and its first row and column are initialized with first row and column of the original matrix, using the first two loops.
2. The set of nested loops while(i<n){ while(j<m) are used to compute order of the largest sub-square matrix.
3. The loops while(i<n){ while(j<m), find out the order of the largest square sub-matrix and the maximum row and column index are stored in max_i and max_j.
4. The loops while(i>(max_i-max)){while(j>(max_j-max)) then print the sub matrix.

Time Complexity: O(nm) where n is the number of rows and m is the number of columns in the matrix respectively.

Runtime Test Cases

 
Case 1 (Simple Test Case):
 
Enter the number of rows
3
Enter the number of columns
4
Enter the Boolean Matrix
0
0
1
1
0
1
1
1
0
0
0
1
The matrix is
0011
0111
0001
Maximum Sub-matrix
11
11
 
Case 2 (Simple Test Case - another example):
 
Enter the number of rows
4
Enter the number of columns
4
Enter the Boolean Matrix
0
1
1
1
0
1
1
1
0
1
1
1
0
1
0
1
The matrix is
0111
0111
0111
0101
Maximum Sub-matrix
111
111
111

Sanfoundry Global Education & Learning Series – Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

« Prev - Java Program to Check if Two Strings are Cyclic Permutations of Each Other

» Next - Java Program to Move All Zeros to the Start of an Array

Related Posts:

Recommended Articles: