MAXIMAL SQUARE

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n]; // dp[i][j] represents the side length of the largest square ending at (i, j)
        int maxLength = 0; // Variable to keep track of the maximum side length
        
        // Initialize the first row and column of dp
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] - '0';
            maxLength = Math.max(maxLength, dp[i][0]);
        }
        
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j] - '0';
            maxLength = Math.max(maxLength, dp[0][j]);
        }
        
        // Calculate dp values for the remaining cells
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        
        return maxLength * maxLength; // Return the area of the largest square
    }
}