221. Maximal Square LeetCode Solution

In this guide, you will get 221. Maximal Square LeetCode Solution with the best time and space complexity. The solution to Maximal Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximal Square solution in C++
Maximal Square solution in Java
Maximal Square solution in Python
Additional Resources

221. Maximal Square LeetCode Solution image

Problem Statement of Maximal Square

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example 1:

Input: matrix = [[“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: matrix = [[“0″,”1”],[“1″,”0”]]
Output: 1

Example 3:

Input: matrix = [[“0”]]
Output: 0

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

221. Maximal Square LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

221. Maximal Square LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

221. Maximal Square LeetCode Solution in Python

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
 # code by PROGIEZ