Leetcode 221. Maximal Square

Seawolf

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

n³ method using 2d matrix presum

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        sum_val = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
        
        for i in range(1, len(sum_val)):
            for j in range(1, len(sum_val[0])):
                sum_val[i][j] = sum_val[i - 1][j] + sum_val[i][j - 1] - sum_val[i - 1][j - 1] + int(matrix[i - 1][j - 1])
        
        m = len(matrix)
        n = len(matrix[0])
        result = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                for size in range(1, min(m - i + 1, n - j + 1) + 1):
                    if sum_val[i + size - 1][j + size - 1] - sum_val[i - 1][j + size - 1] - sum_val[i + size - 1][j - 1] + sum_val[i - 1][j - 1] == (size) * (size):
                        result = max(result, (size) * (size))
        
        return result

n² method using dynamic programming

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        size = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
        result = 0
        for i in range(1, len(matrix) + 1):
            for j in range(1, len(matrix[0]) + 1):
                if matrix[i - 1][j - 1] == '1':
                    size[i][j] = min(size[i - 1][j], size[i][j - 1], size[i - 1][j - 1]) + 1
                    result = max(result, size[i][j])
        return result * result