Java Program to Find the Largest 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

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

  1.  
  2. //Java Program to Find the Largest Square Matrix with all 1's
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class Max1SquareMatrix {
  8.     // Function to find the largest square submatrix and display it.
  9.     static void printSquareSubMatrix(int[][] matrix){
  10.         int m,n;
  11.         n=matrix.length;
  12.         m=matrix[0].length;
  13.         int[][] L = new int[n][m];
  14.         int i,j;
  15.         for(i=0; i<m; i++){
  16.             L[0][i] = matrix[0][i];
  17.         }
  18.         for(i=0; i<n; i++){
  19.             L[i][0] = matrix[i][0];
  20.         }
  21.         i=1;
  22.         while(i<n){
  23.             j=1;
  24.             while(j<m){
  25.                 if(matrix[i][j] == 1){
  26.                     L[i][j] = Math.min(L[i][j-1],
  27.                                        Math.min(L[i-1][j-1],L[i-1][j]))+1;
  28.                 }
  29.                 else{
  30.                     L[i][j] = 0;
  31.                 }
  32.                 j++;
  33.             }
  34.             i++;
  35.         }
  36.         int max = L[0][0];
  37.         int max_i,max_j;
  38.         max_i=max_j=0;
  39.         i=0;
  40.         while(i<n){
  41.             j=0;
  42.             while(j<m){
  43.                 if(L[i][j] > max){
  44.                     max = L[i][j];
  45.                     max_i = i;
  46.                     max_j = j;
  47.                 }
  48.                 j++;
  49.             }
  50.             i++;
  51.         }
  52.         System.out.println("Maximum Sub-matrix");
  53.         i = max_i;
  54.         while(i>(max_i-max)){
  55.             j = max_j;
  56.             while(j>(max_j-max)){
  57.                 System.out.print(matrix[i][j]);
  58.                 j--;
  59.             }
  60.             System.out.println();
  61.             i--;
  62.         }
  63.     }
  64.     // Function to read user input
  65.     public static void main(String[] args) {
  66.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  67.         int rows,columns;
  68.         try{
  69.             System.out.println("Enter the number of rows");
  70.             rows = Integer.parseInt(br.readLine());
  71.             System.out.println("Enter the number of columns");
  72.             columns = Integer.parseInt(br.readLine());
  73.         }
  74.         catch(Exception e){
  75.             System.out.println("An error occurred");
  76.             return;
  77.         }
  78.         int[][] matrix = new int[rows][columns];
  79.         int i,j;
  80.         System.out.println("Enter the Boolean Matrix");
  81.         try{
  82.             for(i=0; i<rows; i++){
  83.                 for(j=0; j<columns; j++){
  84.                     matrix[i][j] = Integer.parseInt(br.readLine());
  85.                 }
  86.             }
  87.         }catch (Exception e){
  88.             System.out.println("An error occurred");
  89.             return;
  90.         }
  91.         System.out.println("The matrix is");
  92.         for(i=0; i<rows; i++){
  93.             for(j=0; j<columns; j++){
  94.                 System.out.print(matrix[i][j]);
  95.             }
  96.             System.out.println();
  97.         }
  98.         if(rows > 0 && columns > 0)
  99.             printSquareSubMatrix(matrix);
  100.     }
  101. }
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.

advertisement

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.

advertisement

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn