22. Maximal Square

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

Example 3:

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

Solution: (Bruteforce)

Algorithm: When we get a square with 1 We expand row, column 1 cell forward

class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {
        int n = matrix.size();
        int m = matrix[0].size();

        int maxSquare = 0;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {

                if (matrix[i][j] == '1')
                {
                    bool isSquare = true;
                    int x = i;
                    int y = j;

                    while (isSquare && x < n && y < m)
                    {
                        for (int p = i; p <= x; p++)
                        {
                            for (int q = j; q <= y; q++)
                            {
                                if (matrix[p][q] == '0')
                                {
                                    isSquare = false;
                                    break;
                                }
                            }
                            if (!isSquare)
                            {
                                break;
                            }
                        }

                        if (isSquare)
                        {

                            int square = (x - i) + 1;
                            if (square > maxSquare)
                            {
                                maxSquare = square;
                            }
                            x++;
                            y++;
                        }
                    }
                }
            }
        }
        return maxSquare * maxSquare;
    }
};

Time Complexity: O(m * n) ^ 2

Solution: (DP)

Algorithm:

class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {

        int n = matrix.size();
        int m = matrix[0].size();

        vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));
        int maxSquare = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (matrix[i - 1][j - 1] == '1')
                {
                    int min1 = min(v[i][j - 1], v[i - 1][j]);
                    int mn = min(min1, v[i - 1][j - 1]);

                    if (mn == 0)
                    {
                        v[i][j] = 1;
                    }
                    else
                    {
                        v[i][j] = 1 + mn;
                    }
                    
                    if (v[i][j] > maxSquare)
                    {
                        maxSquare = v[i][j];
                    }
                }
                else
                {
                    v[i][j] = 0;
                }
            }
        }
        
        return maxSquare * maxSquare;
    }
};

Time Complexity: O(m * n) Space Complexity: O(m+n)