Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

221. Maximal Square - Leetcode Solution

Code Implementation

class Solution:
    def maximalSquare(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * (cols + 1) for _ in range(rows + 1)]
        max_side = 0
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                if matrix[i - 1][j - 1] == '1':
                    dp[i][j] = min(
                        dp[i][j - 1], 
                        dp[i - 1][j], 
                        dp[i - 1][j - 1]
                    ) + 1
                    max_side = max(max_side, dp[i][j])
        return max_side * max_side
      
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, 0));
        int maxSide = 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] = min({dp[i][j-1], dp[i-1][j], dp[i-1][j-1]}) + 1;
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
};
      
class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSide = 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] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}
      
var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const rows = matrix.length, cols = matrix[0].length;
    const dp = Array.from({length: rows + 1}, () => Array(cols + 1).fill(0));
    let maxSide = 0;
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            if (matrix[i - 1][j - 1] === '1') {
                dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
};

Problem Description

Given a 2D binary matrix matrix filled with '0's and '1's, find the largest square containing only '1's and return its area.
  • The input is a matrix of size m x n where each element is either '0' or '1'.
  • You must find the area of the largest square that contains only '1's.
  • Each cell can be used only once and squares must be contiguous (no holes or skips).
  • Return the area (side length squared) of the largest such square.

Thought Process

To solve this problem, first consider the brute-force approach: For every cell in the matrix, try to expand a square as large as possible, checking if all its cells are '1'. This is simple but very inefficient, especially for large matrices. Upon inspection, we notice that for any cell (i, j) to be the bottom-right corner of a square of size k, the cells to the left, above, and diagonally up-left must also be able to form squares of size at least k-1. This observation leads us to dynamic programming, where we can build solutions for larger squares based on solutions for smaller ones. The key shift is from checking every possible square (brute-force) to efficiently building up the answer using previously computed information (dynamic programming).

Solution Approach

  • Step 1: Create a DP table (dp) with dimensions (rows+1) x (cols+1), initialized to 0. This extra row and column simplify boundary checks.
  • Step 2: Iterate through each cell in the original matrix (starting from 1 to handle offsets easily).
  • Step 3: For each cell (i, j) in the matrix:
    • If matrix[i-1][j-1] is '1', set dp[i][j] to 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
    • This formula ensures that the largest square ending at (i, j) is limited by the smallest square among its top, left, and top-left neighbors.
  • Step 4: Keep track of the maximum side length found during the iteration.
  • Step 5: At the end, return the square of the maximum side length as the area.
This approach is efficient because it avoids redundant checks and leverages subproblem solutions.

Example Walkthrough

Consider the following input matrix:

  [
    ['1', '0', '1', '0', '0'],
    ['1', '0', '1', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['1', '0', '0', '1', '0']
  ]
  • We initialize the DP table with zeros, one extra row and column.
  • Iterating through each cell:
    • At position (3,3) (0-based), the cell is '1', and its top, left, and top-left neighbors in the DP table have values 2, 2, and 1, so dp[3][3] = min(2,2,1) + 1 = 2.
    • At position (3,4), the cell is '1', and the neighbors are 2, 1, and 2, so dp[3][4] = min(2,1,2) + 1 = 2.
    • At position (3,5), the cell is '1', and the neighbors are 2, 2, and 2, so dp[3][5] = min(2,2,2) + 1 = 3.
  • The largest value in the DP table is 3, so the largest square has side length 3 and area 9.

Time and Space Complexity

  • Brute-force approach:
    • Time Complexity: O((mn)^2) — For each cell, we may check all possible square sizes.
    • Space Complexity: O(1) — Only constant extra space is needed.
  • Optimized DP approach:
    • Time Complexity: O(mn) — Each cell is visited once and updated in constant time.
    • Space Complexity: O(mn) — For the DP table. This can be reduced to O(n) if only the previous row is kept.

Summary

The maximal square problem is elegantly solved using dynamic programming by recognizing the dependency of a square's size on its neighbors. By building up solutions from the smallest subproblems, we avoid redundant work and achieve an efficient O(mn) solution. The approach is both intuitive and efficient, making it a classic example of dynamic programming in 2D grids.