221. Maximal Square

Hint

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix)
    {
        // Number of rows in the matrix
        // Number of columns in the matrix

        // Create a 2D dp array initialized to 0 with the same dimensions as matrix
        
        // Variable to keep track of the size of the largest square
        
        // Iterate over each cell in the matrix
        for ()
        {
            for ()
            {
                // If we're in the first row or column
                if () 
                {
                    // Initialize dp with the same value as matrix
                }
                // If the current cell is '1'
                else if ()
                {
                    // Calculate the size of the square ending at (i, j)
                }       
                // Update the size of the largest square found so far
            }
        }
        // Return the area of the largest square
    }
};

Solution

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        int d = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i == 0 || j == 0)
                {
                    dp[i][j] = matrix[i][j] - '0';
                }
                else if (matrix[i][j] == '1')
                {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
                d = max(d, dp[i][j]);
            }
        }
        return d * d;
    }
};

• T:
  $O(m\cdot n)$
• S:
  $O(m\cdot n)$

Solution 2 - Space Improved