Maximal Square medium

Problem Statement

Given an m x n binary matrix matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Steps and Explanation

This problem can be efficiently solved using dynamic programming. We'll create a DP table dp of the same dimensions as the input matrix. dp[i][j] will store the size of the largest square ending at matrix[i][j].

1. Initialization:

   • The first row and column of dp are initialized directly from the input matrix. If matrix[i][j] is '1', dp[i][j] is 1; otherwise, it's 0.

2. Iteration:

   • We iterate through the remaining cells of the matrix (starting from i=1, j=1).
   • For each cell matrix[i][j], if it's a '1', we calculate the size of the largest square ending at this cell using the following formula: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
   • This formula considers the squares ending at the cell above, to the left, and diagonally above and to the left. The minimum of these three values plus 1 gives the size of the largest square ending at the current cell. If matrix[i][j] is '0', then dp[i][j] remains 0.

3. Finding the Maximum:

   • After iterating through the entire matrix, we find the maximum value in the dp table. The square of this maximum value is the area of the largest square.

Code (Java)

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxSide = 0;

        // Initialize first row and column
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxSide = 1;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                maxSide = 1;
            }
        }

        // Iterate and fill the dp table
        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], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        return maxSide * maxSide;
    }
}

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the input matrix. We iterate through the matrix once to build the DP table.
• Space Complexity: O(m*n), as we use a DP table of the same size as the input matrix. We could potentially optimize this to O(n) space by using only one row of the DP table, but this would make the code slightly more complex.