Extremely Simple Java Solution :)


  • 239
    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;
    }

  • 29

    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!

  • 23
    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)


  • 0
    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!

  • 0
    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).


  • 17

    alt text


  • 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;
        }
    

  • 1

    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.