maximal-sq.py

def maximalSquare(matrix):

    if matrix is None or len(matrix)==0:
        return 0

    max_sq = 0

    height, width = len(matrix), len(matrix[0])
    dp = [[0 for i in range(width+1)] for j in range(height+1)]

    for i in range(1, height+1):
        for j in range(1, width+1):

            if matrix[i-1][j-1] == "1":
                dp[i][j] =  min([dp[i-1][j], dp[i][j-1], dp[i-1][j-1]]) +1
                max_sq   =  max(max_sq, dp[i][j])

    return max_sq**2