Skip to content

221. Maximal Square 👍

Approach 1: 2D DP

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maximalSquare(vector<vector<char>>& matrix) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    int maxLength = 0;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (i == 0 || j == 0 || matrix[i][j] == '0')
          dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
        else
          dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
        maxLength = max(maxLength, dp[i][j]);
      }

    return maxLength * maxLength;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int maximalSquare(char[][] matrix) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int[][] dp = new int[m][n];
    int maxLength = 0;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        if (i == 0 || j == 0 || matrix[i][j] == '0')
          dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
        else
          dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
        maxLength = Math.max(maxLength, dp[i][j]);
      }

    return maxLength * maxLength;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maximalSquare(self, matrix: List[List[str]]) -> int:
    m = len(matrix)
    n = len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    maxLength = 0

    for i in range(m):
      for j in range(n):
        if i == 0 or j == 0 or matrix[i][j] == '0':
          dp[i][j] = 1 if matrix[i][j] == '1' else 0
        else:
          dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1]
                         [j], dp[i][j - 1]) + 1
        maxLength = max(maxLength, dp[i][j])

    return maxLength * maxLength

Approach 2: 1D DP

  • Time: $O(mn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maximalSquare(vector<vector<char>>& matrix) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<int> dp(n);
    int maxLength = 0;
    int prev = 0;  // dp[i - 1][j - 1]

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        const int cache = dp[j];
        if (i == 0 || j == 0 || matrix[i][j] == '0')
          dp[j] = matrix[i][j] == '1' ? 1 : 0;
        else
          dp[j] = min({prev, dp[j], dp[j - 1]}) + 1;
        maxLength = max(maxLength, dp[j]);
        prev = cache;
      }

    return maxLength * maxLength;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int maximalSquare(char[][] matrix) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int[] dp = new int[n];
    int maxLength = 0;
    int prev = 0; // dp[i - 1][j - 1]

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        final int cache = dp[j];
        if (i == 0 || j == 0 || matrix[i][j] == '0')
          dp[j] = matrix[i][j] == '1' ? 1 : 0;
        else
          dp[j] = Math.min(prev, Math.min(dp[j], dp[j - 1])) + 1;
        maxLength = Math.max(maxLength, dp[j]);
        prev = cache;
      }

    return maxLength * maxLength;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maximalSquare(self, matrix: List[List[chr]]) -> int:
    m = len(matrix)
    n = len(matrix[0])
    dp = [0] * n
    maxLength = 0
    prev = 0  # dp[i - 1][j - 1]

    for i in range(m):
      for j in range(n):
        cache = dp[j]
        if i == 0 or j == 0 or matrix[i][j] == '0':
          dp[j] = 1 if matrix[i][j] == '1' else 0
        else:
          dp[j] = min([prev, dp[j], dp[j - 1]]) + 1
        maxLength = max(maxLength, dp[j])
        prev = cache

    return maxLength * maxLength