Maximal Square

Share

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

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
Example 2
Input: [["0","1"],["1","0"]] → Output: 1

Solution Approach

dp[i][j] = side length of largest square with bottom-right corner at (i,j). If matrix[i][j]==1: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

  • dp[i][j] = 0 if matrix[i][j] == 0.
  • Otherwise: dp[i][j] = min(left, top, top-left diagonal) + 1.
  • Track maxSide = max(dp[i][j]).
  • Return maxSide * maxSide.
Java
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length, maxSide = 0;
        int[][] dp = new int[m + 1][n + 1];
        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(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)