Maximal Square medium

Problem Statement

Given an m x n binary 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

1. Initialization: Create a DP table dp of the same size as the input matrix. Initialize the first row and column of dp to be the same as the corresponding row and column of the input matrix (converted to integers). This is because the largest square ending at a cell in the first row or column can be at most 1x1.

2. Iteration: Iterate through the remaining cells of the matrix (starting from index [1, 1]). For each cell matrix[i][j], if matrix[i][j] is '1':

   • Calculate dp[i][j] as the minimum of dp[i-1][j], dp[i][j-1], and dp[i-1][j-1], plus 1. This represents the size of the largest square ending at this cell. The minimum is taken because the square can only be as large as the smallest square to its top, left, and top-left.

3. Finding the Maximum: After the iteration, iterate through the dp table and find the maximum value. The square of this maximum value will be the area of the largest square.

Explanation

The dynamic programming approach efficiently solves this problem by building up the solution from smaller subproblems. dp[i][j] stores the side length of the largest square ending at position (i, j). We don't need to repeatedly check squares for every possible position. The minimum among the three neighbors (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) ensures that we find the largest possible square whose bottom-right corner is at matrix[i][j].

Code

using System;

public 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];
        int maxSide = 0;

        // Initialize first row and column
        for (int i = 0; i < m; i++) {
            dp[i, 0] = matrix[i][0] - '0';
            maxSide = Math.Max(maxSide, dp[i, 0]);
        }
        for (int j = 0; j < n; j++) {
            dp[0, j] = matrix[0][j] - '0';
            maxSide = Math.Max(maxSide, dp[0, j]);
        }

        // Iterate through the rest of the matrix
        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 matrix. We iterate through the matrix once to build the DP table.
• Space Complexity: O(m * n), due to the DP table used to store intermediate results. This could be optimized to O(n) space by using only one row of the DP table (but the code becomes slightly more complex).