221. Maximal Square

Description

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Output: 4

Solutions

Solution 1

/**
 * Time complexity : O((m*n)^2)
 * Space complexity : O(1)
 */

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        
        int rows = matrix.length, 
            cols = matrix[0].length;
        int maxsqlen = 0;
        
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(matrix[i][j] == '1') {
                    int sqlen = 1;
                    boolean flag = true;
                    while(sqlen + i < rows && sqlen + j < cols && flag) {
                        for(int k = j; k <= sqlen + j; k++) {
                            if (matrix[i + sqlen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for(int k = i; k <= sqlen + i; k++) {
                            if (matrix[k][j + sqlen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if(flag) sqlen++;
                    }
                    if(maxsqlen < sqlen) {
                        maxsqlen = sqlen;
                    }
                }
            }
        }
        return maxsqlen * maxsqlen;
    }
}

Solution 2

/**
 * Time complexity : O(m*n)
 * Space complexity : O(m*n)
 */

class Solution {
    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+1][col+1];
        int sqlen = 0;
        
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                if(matrix[i-1][j-1] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], 
                                           Math.min(dp[i][j-1], dp[i-1][j]));
                    sqlen = Math.max(sqlen, dp[i][j]);
                }
            }
        }
        return sqlen * sqlen;
    }
}

Solution 3

/**
 * Time complexity : O(m*n), where m = row length, n = col length
 * Space complexity : O(n), where n = col length
 */
 
 class Solution {
    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[col+1];
        int sqlen = 0, prev = 0;
        
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                int tmp = dp[j];
                if(matrix[i-1][j-1] == '1') {
                    dp[j] = 1 + Math.min(dp[j], Math.min(dp[j-1], prev));
                    sqlen = Math.max(sqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = tmp;
            }
        }
        return sqlen * sqlen;
    }
}

Follow up