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.

For example, given the following matrix:

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

Return 4.

The Idea: Harness the power of DP. Store the matrix as a submatrix of an n+1 larger matrix. Then, for each element in the submatrix, find the min(left, right, diag) + 1. The above example will in effect become:

 0 0 0 0 0 0
 0 1 0 1 0 0
 0 1 0 1 1 1
 0 1 1 1 2 2 
 0 1 0 0 1 0

The intuition is that we want to find a way that tells us what size our square matrix is by looking it's surrounding neighbors. A 4 by 4 square for example, can become decomposed as follows:

0 0 0 0 0
0 1 1 1 1 
0 1 2 2 2
0 1 2 3 3
0 1 2 3 4

Notice how every number is true for every subsquare in the matrix. Once we know what matrix we want to generate, we can reverse engineer a formula (min(left, right, diag) + 1) that makes this true.

Complexity: O(2n) time (extra time converting char matrix to int matrix) and O(1) space

import numpy as np

class Solution:
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """

        if not matrix:
            return 0

        Matrix = np.zeros((len(matrix) + 1, len(matrix[0]) + 1))
        Matrix[1:Matrix.shape[0], 1:Matrix.shape[1]] = np.array(matrix, dtype=int)
        the_max = 0

        for i in range(1, Matrix.shape[0]):
            for j in range(1, Matrix.shape[1]):
                if Matrix[i][j] == 1:
                    Matrix[i][j] = min(Matrix[i - 1, j], Matrix[i - 1, j - 1], Matrix[i, j - 1]) + 1
                    the_max = max(the_max, int(Matrix[i][j]))
        return the_max*the_max


t1 = [['1', '0', '1', '0', '0'],
      ['1', '0', '1', '1', '1'],
      ['1', '1', '1', '1', '1'],
      ['1', '0', '0', '1', '0']]

obj = Solution()
print(obj.maximalSquare(t1))