# 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

# Solution

Approach 1: DP.

# Code (Python)

Approach 1:

    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # DP. Use 2 rows to keep track of the max square for each cell (or better -- just 1 row, but keep the previous value in a temp variable)
        # sides[i][j] = min(sides[i-1][j], sides[i][j-2], sides[i-1][j-1]) + 1
        if not matrix or not matrix[0]:
            return 0

        sides = [0 if element == '0' else 1 for element in matrix[0]]
        max_side = max(sides)
        
        for row_num in range(1, len(matrix)):
            prev = sides[0]
            sides[0] = 0 if matrix[row_num][0] == '0' else 1
            for col_num in range(1, len(matrix[0])):
                temp_prev = sides[col_num]
                if matrix[row_num][col_num] == '1':
                    sides[col_num] = 1 + min(
                        prev,
                        sides[col_num],
                        sides[col_num-1])
                else:
                    sides[col_num] = 0
                prev = temp_prev
                
            max_side = max(max(sides), max_side)
        
        return max_side * max_side

# Code (C++)

Approach 1:

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        if (n == 0) return 0;
/*
        int len[m+1][n+1] = {0};
        for (int i = 0; i <= m; ++i) len[i][0] = 0;
        for (int j = 0; j <= n; ++j) len[0][j] = 0;
*/
        int len[n+1] = {0};
        int prev = 0;

        int maxLen = 0;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                int temp = len[j]; // need to be here.
                if (matrix[i-1][j-1] == '1')
                {
/*
                    len[i][j] = 1 + std::min(
                        std::min(len[i-1][j], len[i][j-1]),
                        len[i-1][j-1]);
                    maxLen = std::max(maxLen, len[i][j]);
*/
                    len[j] = 1 + std::min(std::min(len[j], prev), len[j-1]);
                    maxLen = std::max(maxLen, len[j]);
                }
                else
                {
                    len[j] = 0; // need to assign 0 to overwrite the previous value.
                }
                prev = temp; // need to be here.
            }
        }
        return maxLen * maxLen;
    }
};