Problem statement

Given an m × n binary matrix filled with 0s and 1s, find the largest square made entirely of 1s 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

• 1 <= matrix.length, matrix[i].length <= 8
• matrix[i][j] is 0 or 1.

Hints for Maximal Square

1. Hint 1

   Let dp[r][c] be the side of the largest all-ones square whose bottom-right corner is (r, c).

2. Hint 2

   A square of side k there requires squares of side k - 1 ending above, to the left, and up-left — so take the minimum of those three and add one.

3. Hint 3

   The answer is the largest side squared, not the largest side.

How to solve Maximal Square

Let dp[r][c] be the side of the largest all-ones square with bottom-right corner at (r, c); it is 1 + min of the three squares ending above, left, and up-left.

Approach

1. For each cell that is 1: on the first row or column set dp = 1, else dp = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]).
2. Track the largest dp value.
3. Return best².

Why it works

A k × k square ending at (r, c) exists iff (k-1) × (k-1) squares end at each of the three neighbours — those cover the square minus its bottom-right cell — so the minimum of the three bounds the side and the recurrence is exact.

Complexity

• Time — O(m · n)
• Space — O(m · n), reducible to two rows

Pitfalls

• Return the area, not the side.

Reference solution

Python

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

Java

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

C++

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

JavaScript

var maximalSquare = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const dp = [];
    for (let r = 0; r < m; r++) dp.push(new Array(n).fill(0));
    let best = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (matrix[r][c] === 1) {
                if (r === 0 || c === 0) dp[r][c] = 1;
                else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1;
                if (dp[r][c] > best) best = dp[r][c];
            }
        }
    }
    return best * best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium