LeetCode [221] Maximal Square

 221. Maximal Square

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

//C++ class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int m = matrix.size(); if(m==0) return 0; int n = matrix[0].size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); int ret = 0; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(matrix[i-1][j-1]=='1'){ int x = dp[i][j-1]; int y = dp[i-1][j]; if(x!=y){ dp[i][j] = min(x, y) + 1; }else{ dp[i][j] = x + (matrix[i-x-1][j-y-1]=='1'?1:0); } ret = max(ret, dp[i][j]*dp[i][j]); } } } return ret; } }; class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int m = matrix.size(); if(m==0) return 0; int n = matrix[0].size(); vector<int> dp(n+1, 0); int ret = 0; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(matrix[i-1][j-1]=='1'){ int x = dp[j-1]; int y = dp[j]; if(x!=y){ dp[j] = min(x, y) + 1; }else{ dp[j] = x + (matrix[i-1-x][j-1-y]=='1'?1:0); } }else{ dp[j] = 0; } ret = max(ret, dp[j]*dp[j]); } } return ret; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

//Java class Solution { public int maximalSquare(char[][] matrix) { int m = matrix.length; if(m==0) return 0; int n = matrix[0].length; if(n==0) return 0; int dp[][] = new int[m+1][n+1]; int ret = 0; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(matrix[i-1][j-1] == '1'){ int x = dp[i][j-1]; int y = dp[i-1][j]; if(x!=y){ dp[i][j] = Math.min(x,y)+1; }else{ dp[i][j] = x;//x==y; if(matrix[i-1-x][j-1-y]=='1'){ dp[i][j]++; } } } ret = Math.max(ret, dp[i][j]*dp[i][j]); } } return ret; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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