Maximal Square

#leetcode #dsa #theabbie

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

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

SOLUTION:

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        biggest = 0
        for i in range(m):
            for j in range(n):
                for w in range(biggest, min(m - i, n - j) + 1):
                    valid = True
                    for p in range(w):
                        for q in range(w):
                            if matrix[i + p][j + q] != "1":
                                valid = False
                                break
                        if not valid:
                            break
                    if valid:
                        biggest = max(biggest, w)
                    else:
                        break
        return biggest * biggest