This Java program finds the largest square that contains only 1s in a binary matrix. It uses dynamic programming to efficiently calculate the size of the largest square sub-matrix filled entirely with 1s.
Java Program
public class LargestSquareOfOnes {
// Function to find the largest square sub-matrix containing only 1s
public static int largestSquare(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int rows = matrix.length;
int cols = matrix[0].length;
int maxSize = 0;
// Create a DP table to store the size of the largest square ending at each position
int[][] dp = new int[rows][cols];
// Iterate through the matrix
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
if (i == 0 || j == 0) {
dp[i][j] = 1; // First row and first column
} else {
// DP formula: Take the minimum of the three neighboring cells and add 1
dp[i][j] = Math.min(dp[i – 1][j], Math.min(dp[i][j – 1], dp[i – 1][j – 1])) + 1;
}
// Update maxSize if the new square is larger
maxSize = Math.max(maxSize, dp[i][j]);
}
}
}
return maxSize; // Return the size of the largest square
}
public static void main(String[] args) {
int[][] matrix = {
{1, 0, 1, 0, 0},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 0, 0, 1, 0}
};
// Find and print the size of the largest square
int result = largestSquare(matrix);
System.out.println(“The size of the largest square containing only 1s is: ” + result);
}
}
Explanation of the Program Structure
This program uses dynamic programming to solve the problem of finding the largest square of 1s in a binary matrix. The main idea is to build a dp (dynamic programming) table, where each element represents the size of the largest square ending at that particular position in the matrix.
- largestSquare function: This function takes a 2D binary matrix as input and returns the size of the largest square sub-matrix containing only 1s. It uses dynamic programming to build a table that stores the size of the largest square for each cell.
- DP table: The dynamic programming table
dp[i][j]is calculated as the minimum of the values from three neighboring cells: the cell above, the cell to the left, and the cell diagonally above-left. The formula for updating thedptable is:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. - Base case: For cells in the first row or first column, the largest square is simply the value of the cell itself (either 0 or 1). This is because a square cannot extend beyond the matrix boundary.
- main function: This function initializes a sample binary matrix and calls the
largestSquarefunction. It then prints the size of the largest square containing only 1s.
Step-by-Step Process:
- We initialize a
dptable of the same size as the input matrix. - We iterate through each element of the matrix. For each element
matrix[i][j], if it is 1, we calculate the largest square that can end at that position using the DP formula. - We keep track of the maximum square size encountered during the iteration.
- Once the matrix is fully traversed, the largest square size is returned and printed.
Example:
Consider the following 4×5 binary matrix:
{1, 0, 1, 0, 0},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 0, 0, 1, 0}
The largest square sub-matrix containing only 1s has a size of 2×2. The dp table for this matrix will look like this:
{1, 0, 1, 0, 0},
{1, 0, 1, 1, 1},
{1, 1, 2, 2, 2},
{1, 0, 0, 1, 0}
The largest square of 1s has a size of 2×2, which is returned by the program.
Conclusion:
This Java program provides an efficient solution to finding the largest square containing only 1s in a binary matrix. The time complexity of the solution is O(n * m), where n is the number of rows and m is the number of columns in the matrix. This makes it suitable for solving the problem even with larger matrices.
