Example: Max Square Submatrix with All 1s in Java

// Max Square Submatrix with All 1s
import java.lang.Math; // For Math.min

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Define the input binary matrix
        char[][] matrix1 = {
            {'1', '0', '1', '0', '0'},
            {'1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '0'}
        };

        char[][] matrix2 = {
            {'0', '1'},
            {'1', '0'}
        };

        char[][] matrix3 = {
            {'0'}
        };

        // Step 2: Call the method to find the maximum square for each matrix
        System.out.println("Matrix 1:");
        System.out.println("Max square area: " + maximalSquare(matrix1)); // Expected: 9
        
        System.out.println("\nMatrix 2:");
        System.out.println("Max square area: " + maximalSquare(matrix2)); // Expected: 1

        System.out.println("\nMatrix 3:");
        System.out.println("Max square area: " + maximalSquare(matrix3)); // Expected: 0
    }

    /**
     * Finds the maximal square submatrix of '1's and returns its area.
     * @param matrix The input binary matrix.
     * @return The area of the maximal square submatrix.
     */
    public static int maximalSquare(char[][] matrix) {
        // Step 1: Handle edge cases for empty or invalid matrices
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSide = 0; // Stores the maximum side length found so far

        // Step 2: Initialize a DP table. dp[i][j] will store the side length of
        // the largest square with all '1's ending at (i-1, j-1) in the original matrix.
        // We use an extra row/column for easier boundary handling (0-indexed matrix, 1-indexed dp table logic).
        int[][] dp = new int[rows + 1][cols + 1];

        // Step 3: Iterate through the matrix to fill the DP table
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                // If the current cell in the original matrix is '1'
                if (matrix[i - 1][j - 1] == '1') {
                    // The side length of the square ending at (i-1, j-1) is 1 plus the minimum
                    // of the squares ending at its top, left, and top-left neighbors.
                    // This is because a square ending at (i,j) must have all '1's
                    // at (i-1,j), (i,j-1), and (i-1,j-1) to form a larger square.
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                    
                    // Update the maximum side length found
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
                // If the current cell is '0', dp[i][j] remains 0 (default initialized value)
                // because a square of '1's cannot end here.
            }
        }

        // Step 4: The result is the area, which is maxSide * maxSide
        return maxSide * maxSide;
    }
}