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

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

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

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);

`}`

`}`

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.

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

**Next Steps:**

- Get Free Certificate of Merit in Java Programming
- Participate in Java Programming Certification Contest
- Become a Top Ranker in Java Programming
- Take Java Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Buy Programming Books
- Practice Information Technology MCQs
- Practice Programming MCQs
- Buy Java Books
- Apply for Information Technology Internship