Question

Formatted question description: https://leetcode.ca/all/221.html

 221	Maximal Square

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

 For example, given the following matrix:

 1 0 1 0 0
 1 0 1 1 1
 1 1 1 1 1
 1 0 0 1 0

 Return 4.


----- Test Case -----
 Input: [["1"]]
 Expected: 1

 Input: [["0"]]
 Expected: 0

 @tag-dp

Algorithm

The brute force method, mechanism of this method is to treat each point in the array as the left vertex of a square and scan to the bottom right to find the largest square.

But, there is better solution.

After establishing the cumulative sum array, we start to traverse every position of the two-dimensional array. For any position (i, j), we traverse all squares from that position to (0,0), the number of squares is min(i,j)+1,

Because of the cumulative sum matrix, we can quickly find the sum of any area, so we can quickly get the sum of all sub-squares,

Compare whether the sum of the square is equal to the square of the side length. The equality means that the numbers in the square are all 1. Then update the result.

Code

Java

public class Maximal_Square {

    // Time complexity : O(mn). Single pass.
    // Space complexity : O(mn). Another matrix of same size is used for dp.
    public class Solution_dp {
        public int maximalSquare(char[][] matrix) {

            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }

            int rows = matrix.length;
            int cols = rows > 0 ? matrix[0].length : 0;

            // dp(i,j) represents the side length of the maximum square
            // whose bottom right corner is the cell with index (i,j) in the original matrix.
            int[][] dp = new int[rows + 1][cols + 1];

            int maxsqlen = 0;
            for (int i = 1; i <= rows; i++) {
                for (int j = 1; j <= cols; j++) {
                    if (matrix[i - 1][j - 1] == '1') {

                        dp[i][j] = 1 + Math.min(
                            Math.min(dp[i][j - 1], dp[i - 1][j]),
                            dp[i - 1][j - 1]);

                        maxsqlen = Math.max(maxsqlen, dp[i][j]);
                    }
                }
            }

            return maxsqlen * maxsqlen;
        }
    }


    public class Solution_better_dp {
        public int maximalSquare(char[][] matrix) {

            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }

            int rows = matrix.length;
            int cols = rows > 0 ? matrix[0].length : 0;
            int[] dp = new int[cols + 1];

            int maxsqlen = 0;
            int prev = 0;

            for (int i = 1; i <= rows; i++) {
                for (int j = 1; j <= cols; j++) {
                    int temp = dp[j];
                    if (matrix[i - 1][j - 1] == '1') {
                        dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                        maxsqlen = Math.max(maxsqlen, dp[j]);
                    } else {
                        dp[j] = 0;
                    }
                    prev = temp;
                }
            }

            return maxsqlen * maxsqlen;
        }
    }

    class Solution {
        public int maximalSquare(char[][] matrix) {

            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }

            int result = 0; // worst case, one single pixel

            int row = matrix.length;
            int col = matrix[0].length;

            // largest possible square is fitting the min edge
            int step = Math.min(row, col) - 1; // -1 for index

            // O(): step * (row * col) * (row * col) => (row * col) ^ 2
            while (step >= 0) { // if step==0, then check this very single pixel

                for (int i = 0; i + step < row; i++) {
                    for (int j = 0; j + step < col; j++) {

                        // now check if all 1s for sqaure [i, j] - [i+step, j+step]
                        if (isValidSquare(matrix, i, j, step)) {
                            return (step + 1) * (step + 1); // @note: step is 1 less than actual square edge length
                        }
                    }
                }

                step--;
            }

            return result;
        }

        private boolean isValidSquare(char[][] matrix, int startI, int startJ, int step) {

            for (int i = startI; i <= startI + step; i++) {
                for (int j = startJ; j <= startJ + step; j++) {
                    if (matrix[i][j] != '1') {
                        return false;
                    }
                }
            }

            return true;
        }
    }

}

All Problems

All Solutions