221. Maximal Square.md

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.

Example:

Input:

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

Output: 4

---

Solution

• mine
  • Java
    • DP Runtime: 4 ms, faster than 84.86%, Memory Usage: 42.9 MB, less than 41.00% of Java online submissions

      // O(r*c)time O(1)space
      public int maximalSquare(char[][] matrix) {
          int r, c;
          if (matrix == null || (r = matrix.length) == 0 || (c = matrix[0].length) == 0) {
              return 0;
          }
          int res = 0;
          for (int i = 0; i < r; i++) {
              if (matrix[i][0] != '0') {
                  res = 1;
                  break;
              }
          }
          for (int i = 0; i < c; i++) {
              if (matrix[0][i] != '0') {
                  res = 1;
                  break;
              }
          }
          for (int i = 1; i < r; i++) {
              for (int j = 1; j < c; j++) {
                  if (matrix[i][j] == '0') {
                      continue;
                  }
                  int top = matrix[i - 1][j] - '0';
                  int left = matrix[i][j - 1] - '0';
                  int leftTop = matrix[i - 1][j - 1] - '0';
                  if (leftTop != 0 && top != 0 && left != 0) {
                      leftTop = Math.min(Math.min(left, top), leftTop);
                      matrix[i][j] = (char) (leftTop + 1 + '0');
                  }
                  int d = (matrix[i][j] - '0');
                  res = Math.max(res, d * d);
              }
          }
          return res;
      }
      

---

• the most votes
  • DP Runtime: 4 ms, faster than 84.86%, Memory Usage: 43 MB, less than 27.83% of Java online submissions

    //O(r*c)time O(r*c)space
    public int maximalSquare(char[][] a) {
        if (a == null || a.length == 0 || a[0].length == 0)
            return 0;
    
        int max = 0, n = a.length, m = a[0].length;
    
        // dp(i, j) represents the length of the square 
        // whose lower-right corner is located at (i, j)
        // dp(i, j) = min{ dp(i-1, j-1), dp(i-1, j), dp(i, j-1) }
        int[][] dp = new int[n + 1][m + 1];
    
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
    
        // return the area
        return max * max;
    }
    

---