Largest Square Matrix Problem in Java
Given a Boolean matrix with 0s and 1s our task is to calculate and display the largest square sub-matrix with all of its entries being 1.
Example 1:
Input:
The Matrix
0 0 1 1
0 1 1 1
0 0 0 1
Output:
1 1
1 1
Explanation:
For the given matrix, the largest square matrix that can be obtained with all 1's is printed as output.
Approach: Naïve Approach
Let M[R][C] be the binary matrix that is supplied. The basic idea behind the approach is to create an auxiliary size matrix S[][]. Each entry in S[i][j] conveys the size of the square sub-matrix with all 1s, inclusive of M[i][j], which is the bottom-most and right-most entry in the sub-matrix.
Algorithm:
Step 1: For the provided M[R][C], create a sum matrix S[R][C].
Step 1.1: Transfer the initial row and column from M[][] to S[][] exactly as they are.
Step 1.2: Create S[][] for the remaining entries using the following expressions.
Step 1.2.1: The formula for S[i][j] is min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 if M[i][j] = 1.
Step 1.2.2: Or else M[i][j] = 0 implies that S[i][j] = 0.
Step 2: In S[R][C], determine the maximum entry.
Step 3: Print the M[][] sub-matrix using the coordinates and value of the maximum entry in S[i].
Implementation:
FileName: NaiveApproach.java
import java.io.*;
import java.util.*;
public class NaiveApproach
{
// method to create a square submatrix of maximal size using all 1's
static void MaxSquare(int Mat[][])
{
int i, j;
int row = Mat.length;
int col = Mat[0].length;
int S[][] = new int[row][col];
int maximum_of_s, maximum_i, maximum_j;
// Set S[][]'s first column.
for (i = 0; i < row; i++)
S[i][0] = Mat[i][0];
// Set S[][]'s first row
for (j = 0; j < col; j++)
S[0][j] = Mat[0][j];
// Create more S[][] entries.
for (i = 1; i < row; i++)
{
for (j = 1; j < col; j++)
{
if (Mat[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;
}
}
// Determine the maximum entry in S[][] and its corresponding indices.
maximum_of_s = S[0][0];
maximum_i = 0;
maximum_j = 0;
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
if (maximum_of_s < S[i][j])
{
maximum_of_s = S[i][j];
maximum_i = i;
maximum_j = j;
}
}
}
System.out.println("The largest square matrix with 1's is: ");
for (i = maximum_i; i > maximum_i - maximum_of_s; i--)
{
for (j = maximum_j; j > maximum_j - maximum_of_s; j--)
{
System.out.print(Mat[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args)
{
int Mat[][] = { { 0, 0, 1, 1 }, { 0, 1, 1, 1 }, { 0, 0, 0, 1 }};
MaxSquare(Mat);
}
}
Output:
The largest square matrix with 1's is:
1 1
1 1
Complexity Analysis:
The time complexity is O(m*n), where m and n are the respective numbers of rows and columns in the provided matrix. The space complexity is O(m*n) of the given matrix, where m and n are its row and column numbers, respectively.
Approach: Dynamic Programming
To compute an entry anywhere in the matrix, we only require the current row and the previous row.
The idea is to deal with the task by means of dynamic programming. There is an ideal substructure to the problem. One plus the minimum of the greatest square submatrix ending at M[i][j-1], M[i-1][j], and M[i-1][j-1] will equal the size of the largest square submatrix ending at a cell, M[i][j]. For every possible value of i and j, the resulting value will be the maximum of all square submatrix terminating at M[i][j].
Implementation:
FileName: DynamicApproach.java
import java.util.*;
import java.io.*;
public class DynamicApproach
{
static int row = 3;
static int col = 4;
static void printMaxSubSquare(int Mat[][])
{
int Matrix[][] = new int[2][col], Max = 0;
// initially set all of the matrix's elements to 0.
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < col; j++)
{
Matrix[i][j] = 0;
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
// Compute the temp at the current position
int temp = Mat[i][j];
if (temp != 0)
{
if (j != 0)
{
temp = 1 + Math.min( Matrix[1][j - 1], Math.min(Matrix[0][j - 1], Matrix[1][j]));
}
}
// Add the new temp and save the previous one.
Matrix[0][j] = Matrix[1][j];
Matrix[1][j] = temp;
// Store the maximum square length.
Max = Math.max(Max, temp);
}
}
System.out.print("The largest square matrix with 1's is: \n");
for (int i = 0; i < Max; i++)
{
for (int j = 0; j < Max; j++)
{
System.out.print("1 ");
}
System.out.println();
}
}
public static void main(String[] args)
{
int Mat[][] = { { 0, 0, 1, 1 }, { 0, 1, 1, 1 }, { 0, 0, 0, 1 }};
printMaxSubSquare(Mat);
}
}
Output:
The largest square matrix with 1's is:
1 1
1 1
Complexity Analysis:
The dynamic programming method has an O(m*n) time complexity, where m denotes the number of rows and n is the number of columns in the provided matrix. O(n), where n is the total number of columns in the given matrix, is the space complexity.