Leetcode Maximal Square problem solution

YASH PAL,

In this Leetcode Maximal Square problem solution we have Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s, and return its area.

Leetcode Maximal Square problem solution

Problem solution in Python.

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        
        dp=[]
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j]=int(matrix[i][j])
        
           
        if len(matrix)==1 and len(matrix[0])==1:
            if matrix[0][0]==0:
                return 0
            else:
                return 1  
            
        for i in range(len(matrix)):
            x=[]
            for j in range(len(matrix[0])):
                x.append(0)
            dp.append(x) 
        side=0    
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==1:
                    side=1
                    dp[i][j]=1
        
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                
                if matrix[i][j]==1:
                    dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j], dp[i][j-1]))+1
                    side=max(side,dp[i][j])
        
        return side*side

Problem solution in Java.

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        int res = 0;
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                    res = Math.max(res, dp[i][j]);
                }
                
            }
        }
        
        return res * res;
    }
}

Problem solution in C++.

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size(), res = 0;
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                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;
                    res = max(res, dp[i][j]);
                } 
            }
        }
        
        return res*res;
    }
};

coding problems