An efficient implementation of an algorithm to find the
largest square submatrix consisting entirely of 1's within a given binary
matrix. It utilizes dynamic programming with optimized space complexity by
using two one-dimensional arrays instead of a full auxiliary matrix.
Below, I'll provide a detailed explanation of how the code
works, discuss its efficiency, and suggest potential improvements to enhance
its functionality and robustness.
Java
|
package
com.kartik.matrix; public class
MaxSquareSubMatrix { // Display matrix function public void displayMatrix(int[][]
matrixInput, int row, int cols) { for (int i = 0; i < row; i++) { for (int j = 0; j < cols; j++)
{
System.out.print(matrixInput[i][j] + " "); } System.out.println(); } } // Main method to find the maximum square
submatrix of 1s public void subMatrix(int[][]
baseMatrixInput, int row, int cols) { if (baseMatrixInput == null || row ==
0 || cols == 0) { System.out.println("Invalid
input matrix."); return; } System.out.println("Display base
of matrix:"); displayMatrix(baseMatrixInput, row,
cols); int maxSizeOfMatrix = 0; int maxRow = 0, maxCol = 0; // Optimized auxiliary storage using
two arrays int[] previousRow = new int[cols]; int[] currentRow = new int[cols]; // Initialize first row of the
auxiliary matrix System.arraycopy(baseMatrixInput[0],
0, previousRow, 0, cols); // Process the matrix row by row for (int i = 1; i < row; i++) { for (int j = 0; j < cols; j++)
{ if (j == 0) { currentRow[j] =
baseMatrixInput[i][j]; } else if
(baseMatrixInput[i][j] == 1) { currentRow[j] =
Math.min(previousRow[j - 1], Math.min(previousRow[j], currentRow[j - 1])) +
1; } else { currentRow[j] = 0; } // Keep track of maximum size
square matrix if (currentRow[j] >
maxSizeOfMatrix) { maxSizeOfMatrix =
currentRow[j]; maxRow = i; maxCol = j; } } // Swap rows for next iteration System.arraycopy(currentRow, 0,
previousRow, 0, cols); } if (maxSizeOfMatrix > 0) { System.out.println("Maximum
size square sub-matrix with all 1s: " + maxSizeOfMatrix); displaySubMatrix(maxSizeOfMatrix,
maxRow, maxCol, baseMatrixInput);
displayPositionOfSubMatrix(maxSizeOfMatrix, maxRow, maxCol); } else { System.out.println("No
square sub-matrix with all 1s found."); } } // Display the elements of the largest
submatrix private void displaySubMatrix(int
maxSizeOfMatrix, int maxRow, int maxCol, int[][] baseMatrixInput) { System.out.println("Sub-matrix
with all 1s:"); for (int i = maxRow - maxSizeOfMatrix
+ 1; i <= maxRow; i++) { for (int j = maxCol -
maxSizeOfMatrix + 1; j <= maxCol; j++) {
System.out.print(baseMatrixInput[i][j] + " "); } System.out.println(); } } // Display the positions of the largest
submatrix private void
displayPositionOfSubMatrix(int maxSizeOfMatrix, int maxRow, int maxCol) { System.out.println("Positions of
the sub-matrix:"); for (int i = maxRow - maxSizeOfMatrix
+ 1; i <= maxRow; i++) { for (int j = maxCol -
maxSizeOfMatrix + 1; j <= maxCol; j++) {
System.out.print("[" + i + "," + j + "]
"); } System.out.println(); } } public static void main(String[] args) { int[][] twoDimensionalMatrix = { { 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0 }, { 0, 1, 1, 1, 1, 0 }, { 0, 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1, 1 } }; MaxSquareSubMatrix baseMatrix = new
MaxSquareSubMatrix();
baseMatrix.subMatrix(twoDimensionalMatrix, 5, 6); } } |
Code Explanation
1. Class Definition and Main Method
Ø Class
Name: MaxSquareSubMatrix
Ø Main
Method:
ü
Initializes a sample binary matrix twoDimensionalMatrix.
ü
Creates an instance of MaxSquareSubMatrix.
ü
Calls the subMatrix method with the matrix and
its dimensions.
2. Display Matrix Function (displayMatrix)
Ø Purpose:
Prints the contents of the given matrix.
Ø Parameters:
ü
int[][] matrixInput: The matrix to display.
ü
int row: Number of rows.
ü
int cols: Number of columns.
Ø Implementation:
ü
Uses nested loops to iterate through each
element of the matrix and prints them in a formatted manner.
3. Main Logic to Find the Largest Square Submatrix (subMatrix)
Ø Purpose:
Identifies the largest square submatrix composed entirely of 1's.
Ø Parameters:
ü
int[][] baseMatrixInput: The input binary
matrix.
ü
int row: Number of rows.
ü
int cols: Number of columns.
Ø Implementation
Steps:
a.
Input Validation:
Ø
Checks if the input matrix is null or if its
dimensions are zero. If invalid, it prints an error message and exits the
method.
b.
Display Base Matrix:
Ø
Calls displayMatrix to print the input matrix.
c.
Initialization:
Ø
Variables to keep track of the maximum size (maxSizeOfMatrix)
and position (maxRow, maxCol) of the largest square submatrix found.
Ø
Two one-dimensional arrays, previousRow and currentRow,
are initialized to store intermediate results, optimizing space usage.
Ø
Copies the first row of the input matrix into previousRow
using System.arraycopy.
Ø
Updates maxSizeOfMatrix, maxRow, and maxCol
based on the first row.
d.
Dynamic Programming Computation:
Ø
Iterates over the matrix starting from the
second row.
Ø
For each cell (i, j), it calculates currentRow[j]
as follows:
ü
If j == 0 (first column), currentRow[j] is set
to baseMatrixInput[i][j].
ü
If the current cell in the input matrix is 1, currentRow[j]
is calculated as the minimum of the three neighboring cells plus one: currentRow[j]=min(previousRow[j−1],previousRow[j],currentRow[j−1])+1
ü
If the current cell is 0, currentRow[j] is set
to 0.
Ø
Updates maxSizeOfMatrix, maxRow, and maxCol whenever
a larger square submatrix is found.
Ø
Copies currentRow into previousRow for the next
iteration.
e.
Result Output:
ü
If a square submatrix of size greater than 0 is
found, it calls displaySubMatrix and displayPositionOfSubMatrix to show the
submatrix and its positions.
ü
If no such submatrix is found, it prints an
appropriate message.
4. Display Submatrix Function (displaySubMatrix)
Ø Purpose:
Prints the elements of the largest square submatrix found.
Ø Parameters:
ü
int maxSizeOfMatrix: Size of the largest square
submatrix.
ü
int maxRow: Row index of the bottom-right corner
of the submatrix.
ü
int maxCol: Column index of the bottom-right
corner of the submatrix.
ü
int[][] baseMatrixInput: The input binary
matrix.
Ø Implementation:
ü
Iterates from maxRow - maxSizeOfMatrix + 1 to maxRow
(inclusive) for rows.
ü
Iterates from maxCol - maxSizeOfMatrix + 1 to maxCol
(inclusive) for columns.
ü
Prints each element to display the submatrix.
5. Display Positions Function (displayPositionOfSubMatrix)
Ø Purpose:
Prints the indices of the elements forming the largest square submatrix.
Ø Parameters:
ü
Same as displaySubMatrix, except it doesn't need
the matrix itself.
Ø Implementation:
ü
Uses similar loops as displaySubMatrix but
prints the indices [i, j] instead of the elements.
Example Output
Given the input matrix:
|
0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 |
The program output will be:
Plain text
|
Display base
of matrix: 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 Maximum size
square sub-matrix with all 1s: 3 Sub-matrix
with all 1s: 1 1 1 1 1 1 1 1 1 Positions of
the sub-matrix: [2,2] [2,3]
[2,4] [3,2] [3,3]
[3,4] [4,2] [4,3]
[4,4] |
This indicates that the largest square submatrix of 1's has
a size of 3 and is located ending at position [4,4].
|
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
2 |
2 |
0 |
|
1 |
1 |
1 |
2 |
3 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
2 |
2 |
0 |
|
1 |
1 |
1 |
2 |
3 |
1 |
0 Comments