Largest Square of 1's- Dynamic Programming Solution

Problem:

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:

Approach：

First, make a new matrix with one extra column and one extra row and filled with 0.

Second, if the original Matrix element is 1, we get the minimum of the element adjacency (left, top left and the top one) plus 1 to replace the 0 in the new matrix.

Third, we get the result from the new matrix element number.

My python solution:

def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        nrows = len(matrix)
        ncols = len(matrix[0])
        max_square_len = 0
        dp = [[0] * (ncols + 1) for i in range(nrows + 1)]
        for i in range(1, nrows + 1):
            for j in range(1, ncols + 1):
                if (matrix[i - 1][j - 1] == '1'):
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], 
                    dp[i    - 1][j - 1]) + 1
                    max_square_len = max(max_square_len, dp[i][j])
        return max_square_len ** 2

My JavaScript solution:

(It is slight diffident, we just copy the original matrix, if it is the edge case (i== 0 or j ==0), we don’t do anything( just remain the original result, if it is 1 then the result is 1. Otherwise, we get the minimum of the element adjacency plus 1 as result.

var maximalSquare = function(matrix) {
    let copy = [...matrix]
    let result = 0
    
    for(let i = 0; i < copy.length; i++){
        for (let j = 0; j < copy[i].length; j++){
            if(i == 0 || j == 0 ){
                copy[i][j]=matrix[i][j]
            }else if(matrix[i][j]>0){
                copy[i][j] = 1 + Math.min(copy[i][j-1], copy[i-1] 
                [j], copy[i-1][j-1])
            }
            if(copy[i][j]> result){
               result = copy[i][j]
            }
        }
    }
    return result ** 2
};

Thanks for reading.