Extremely Simple Java Solution :)


  • 255
    public int maximalSquare(char[][] a) {
        if(a.length == 0) return 0;
        int m = a.length, n = a[0].length, result = 0;
        int[][] b = new int[m+1][n+1];
        for (int i = 1 ; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(a[i-1][j-1] == '1') {
                    b[i][j] = Math.min(Math.min(b[i][j-1] , b[i-1][j-1]), b[i-1][j]) + 1;
                    result = Math.max(b[i][j], result); // update result
                }
            }
        }
        return result*result;
    }

  • 32

    Logic :

    Top, Left, and Top Left decides the size of the square. If all of them are same, then the size of square increases by 1. If they're not same, they can increase by 1 to the minimal square. If you take an example and work it out, it'll be much easier to understand when it comes to dynamic programing. :)


  • 0
    P
    This post is deleted!

  • 28
    J

    Can't believe no one has upvoted this yet. This is great solution. Just a thought, if you mention in your explanation that b[i][j] represent the edge length of the largest square ENDING at position (i, j), it would be much clearer.


  • 0
    This post is deleted!

  • 0
    Y

    wow, great ordering! my DP code checks the square beginning at the top left corner. Now i realized how your code reduces time from O(n3) to O(n2)


  • 1
    R

    I just wanted to clarify. Is my understanding correct:

    max[i][j] denotes the max length of a square of 1's whose bottom-right is at i-1,j-1 ?


  • 0
    U
    This post is deleted!

  • 1
    T

    @ rohan99
    I have the same question!
    Can anybody explain this solution in detail?


  • 0
    P

    beautiful, the same idea with mine, but much concise then mine


  • 0
    M

    Fantastic solution


  • 2

    Nice! I happen to find this too. Making dp[i][j] represents state of matrix[i-1][j-1] could save the trouble of boundary initialization. Not sure if this is a general trick for all 2d DP problems or only works in some special case?

    ps: I think this is general for problems such as what's the max, longest XXX and so on where leaving buffer region 0 is ok. But it doesn't work in "min" case which will be wrong if you Math.min(min, 0).


  • 27

    dp[i][j] 代表在以i, j这一格为右下角的正方形边长。
    如果这一格的值也是1,那这个正方形的边长就是他的上面,左手边,和斜上的值的最小边长 +1。因为如果有一边短了缺了,都构成不了正方形。
    alt text

    class Solution {
        public int maximalSquare(char[][] matrix) {
          if(matrix.length == 0) return 0;
          int m = matrix.length, n = matrix[0].length;
          int[][] dp = new int[m + 1][n + 1];
       
          int maxEdge = 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(Math.min(dp[i - 1][j], dp[i][j - 1]),dp[i - 1][j - 1]) + 1;
                maxEdge = Math.max(maxEdge, dp[i][j]);
              }
            }
          }
          
          return maxEdge * maxEdge;  
        }
    }

  • 0
    B

    @hot13399 Thanks for the explanation. Really smart solution!


  • 0

    Brilliant solution! DP based on the side instead of the area is the key point, as it is square instead of rectangle! Vote up!


  • 0
    O

    Brilliant Solution!


  • 0

    pretty the same except starting index

        public int maximalSquare(char[][] matrix) {
            if (matrix == null || matrix.length == 0) {
                return 0;
            }
            int row = matrix.length, col = matrix[0].length;
            int[][] dp = new int[row][col];
            int len = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    int value = matrix[i][j] - '0';
                    if (value == 0)
                        continue;
                    if (i == 0 || j == 0) {
                        dp[i][j] = value;
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    }
                    len = Math.max(len, dp[i][j]);
                }
            }
            return len * len;
        }
    

  • 2

    Same idea, but using O(n) space complexity rathen than O(mn)

    public 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 max = 0;
            //initialization
            int[][] dp = new int[2][n+1];
    
            for(int i = 1; i <= m ; i++){
                for(int j = 1; j <= n; j++){
                    
                    if(matrix[i-1][j-1] == '0') {
                        dp[i%2][j] = 0;
                    }else{
                        dp[i%2][j] = Math.min( Math.min(dp[(i+1)%2][j-1], dp[(i+1)%2][j]) , dp[i%2][j-1]) + 1;
                    }
    
                    max = dp[i%2][j] > max ? dp[i%2][j] : max;
                }
            }
    
            return max*max;
        }
    }
    

  • 0

    @Hellokitty_2015 Maybe take the min of (m,n)? instead of n


  • 0

    @jaqenhgar you are right, that depends on which corner you choose to start~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.