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

Difficulty: interview

Starter code:

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        

Solutions:
class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if not matrix:
             return 0
 
         m, n = len(matrix), len(matrix[0])
         dp = [int(matrix[i][0]) for i in range(m)]
         vmax = max(dp)    
         pre = 0   
         for j in range(1, n):
             pre, dp[0] = int(matrix[0][j-1]), int(matrix[0][j])
             for i in range(1, m):
                 cur = dp[i]
                 dp[i] = 0 if matrix[i][j] == '0' else (min(dp[i-1], dp[i], pre) + 1) 
                 pre = cur
             vmax = max(vmax, max(dp))
         return vmax ** 2

class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if len(matrix) == 0 or len(matrix[0]) == 0: return 0
         n, m = len(matrix), len(matrix[0])
         dp = [[0 for i in range(m)] for j in range(n)]
         for i in range(n): dp[i][0] = int(matrix[i][0])
         for j in range(m): dp[0][j] = int(matrix[0][j])
         for i in range(1, n):
             for j in range(1, m):
                 if (matrix[i][j] == '1'):
                     dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
         ans = 0
         for i in range(n):
             ans = max(ans, max(dp[i]))
         return ans ** 2

class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if not matrix: return 0
         rows, cols = len(matrix), len(matrix[0])
         dp = list(map(int, matrix[0][:]))
         maxLen = 1 if sum(dp) > 0 else 0
         for i in range(1, rows):
             tmp = dp[0]
             dp[0] = int(matrix[i][0])
             maxLen = max(maxLen, dp[0])
             pre = tmp
             for j in range(1, cols):
                 tmp = dp[j]
                 if matrix[i][j] == '1':
                     dp[j] = min(dp[j], dp[j - 1], pre) + 1
                     maxLen = max(maxLen, dp[j])
                 else:
                      dp[j] = 0
                 pre = tmp
         return maxLen * maxLen

class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if not matrix: return 0
         rows, cols = len(matrix), len(matrix[0])
         dp = [0] * cols
         maxLen = 1 if sum(dp) > 0 else 0
         for i in range(0, rows):
             for j in range(0, cols):
                 if matrix[i][j] == '1':
                     if j == 0:
                         dp[j] = int(matrix[i][j])
                     else:
                         k = min(dp[j], dp[j - 1])
                         dp[j] = (k + 1) if matrix[i - k][j - k] == '1' else k
                     maxLen = max(maxLen, dp[j])
                 else:
                     dp[j] = 0
         return maxLen * maxLen

class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if not matrix or len(matrix) == 0:
             return 0
         m = len(matrix)
         n = len(matrix[0])
         dp = [[0 for i in range(n)] for j in range(m)]
         dp[0] = list(map(lambda x: int(x), matrix[0]))
         maxLength = 1 if 1 in dp[0] else 0
         for i in range(1, m):
             dp[i][0] = int(matrix[i][0])
             if dp[i][0] == 1:
                 maxLength = 1
         for i in range(1, m):
             for j in range(1, n):
                 if matrix[i][j] == '0':
                     dp[i][j] = 0
                 else:
                     dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                     maxLength = max(maxLength, dp[i][j])
         return maxLength ** 2

class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         m, n = len(matrix), len(matrix[0]) if matrix else 0
         dp = [0]*n
         best = 0
         for r in range(m):
             ndp = [0]*n
             for c in range(n):
                 if matrix[r][c] == '1':
                     ndp[c] = min(dp[c-1], dp[c], ndp[c-1])+1 if r and c else 1
                     if ndp[c] > best:
                         best = ndp[c]
             dp = ndp
         return best**2

class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         
         
         g = 0
         #li[i][j] is the largest square whose right-lower conner lands at [i][j]
         li = [[0 for a in x] for x in matrix] 
         
         for i in range(0,len(matrix)):
             for j in range(0,len(matrix[0])):
                 c = int(matrix[i][j])
                 if c==0:
                     li[i][j]=0
                     continue
                 if i==0 or j==0:
                     li[i][j] = c
                     if c>g:
                         g=c
                     continue
                 
             
                 m = min(li[i-1][j], li[i][j-1])
                 if li[i-1][j-1]<=m:
                     li[i][j] = 1+li[i-1][j-1]
                 else:
                     li[i][j] = 1+m
                 
                 if li[i][j]>g:
                     g = li[i][j]
                 
             
         return g**2
                 
                  
                     
                 


class Solution:
     def maximalSquare(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if len(matrix) == 0 or len(matrix[0]) == 0:
             return 0
         
         dp = [[0 for i in range(len(matrix[0]))] for i in range(len(matrix))]
         
         largest = 0;
         for i in range(len(matrix)):
             dp[i][0] = int(matrix[i][0])
             largest = max(largest, dp[i][0])
             
         for j in range(len(matrix[0])):
             dp[0][j] = int(matrix[0][j])
             largest = max(largest , dp[0][j])
             
         
         
         for i in range(1, len(matrix)):
             for j in range(1, len(matrix[0])):
                 if matrix[i][j] == '1':
                     if dp[i - 1][j] >= dp[i - 1][j - 1] and dp[i][j - 1] >= dp[i - 1][j - 1]:
                         dp[i][j] = dp[i - 1][j - 1] + 1
 
                     else:
                         dp[i][j] = min(int(dp[i - 1][j]), int(dp[i][j - 1])) + 1
                 else:
                     dp[i][j] = 0
                 
                 largest = max(largest, dp[i][j])
         
         
         return largest * largest