Maximal Square

mediumAmazon-tagged: Trees & Matrix (mock day)79 stepsJava · Python · C++

Find the largest square of 1s. dp[r][c] is the side of the largest all-1 square whose bottom-right corner is (r, c): one more than the smallest of its top, left and top-left neighbours. Return the largest side squared.

▶ Watch the animated trace

Traced input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] → 4. Original problem: neetcode.io/problems/maximal-square

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Can use one row.

Key idea

A square of side s ending at (r, c) needs squares of side s − 1 ending above, left and diagonally.
So the side is limited by the smallest of the three, plus one.
A padded (m+1)×(n+1) table avoids border checks.

Common mistakes

Returning the side instead of the area.
Using max instead of min.

Solution

Java

int maximalSquare(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length, best = 0;
    int[][] dp = new int[m + 1][n + 1];
    for (int r = 1; r <= m; r++) {
        for (int c = 1; c <= n; c++) {
            if (matrix[r - 1][c - 1] == '1') {
                dp[r][c] = 1 + Math.min(dp[r - 1][c - 1], Math.min(dp[r - 1][c], dp[r][c - 1]));
                best = Math.max(best, dp[r][c]);
            }
        }
    }
    return best * best;
}

Python

def maximalSquare(matrix: List[List[str]]) -> int:
    m, n, best = len(matrix), len(matrix[0]), 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for r in range(1, m + 1):
        for c in range(1, n + 1):
            if matrix[r - 1][c - 1] == '1':
                dp[r][c] = 1 + min(dp[r - 1][c - 1], dp[r - 1][c], dp[r][c - 1])
                best = max(best, dp[r][c])
    return best * best

C++

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));
    for (int r = 1; r <= m; r++) {
        for (int c = 1; c <= n; c++) {
            if (matrix[r - 1][c - 1] == '1') {
                dp[r][c] = 1 + min({dp[r - 1][c - 1], dp[r - 1][c], dp[r][c - 1]});
                best = max(best, dp[r][c]);
            }
        }
    }
    return best * best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All zeros No square.	`matrix = [[0, 0]]`	`0`
Single 1 Diagonal 1s don't form a 2×2.	`matrix = [[0, 1], [1, 0]]`	`1`
All ones The whole matrix.	`matrix = [[1, 1], [1, 1]]`	`4`