Back to solutions

Maximal Square

MediumDynamic Programming

Find the area of the largest square containing only 1s in a binary matrix.

Open problem
Constraints
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'

DP of largest square ending at a cell

Time O(m * n)Space O(m * n)

dp[i][j] is the side of the largest all-ones square whose bottom-right is (i, j). For a 1 cell it is one plus the minimum of the top, left, and top-left neighbors. Track the maximum side.

#include <bits/stdc++.h>
using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), best = 0;
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (matrix[i-1][j-1] == '1') {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                best = max(best, dp[i][j]);
            }
    return best * best;
}