Command Palette

Search for a command to run...

Hectal
Problem 29.6 · DP on GridsMedium

Maximal Square

PatternGrid DP

What it teaches: A state that measures a shape: the largest square ending at each cell.

Practise it on judges as “Maximal Square”.

The problem

In a binary matrix of '0' and '1', return the area of the largest square containing only '1's.

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

Constraints

  • 1 ≤ m, n ≤ 300

Pattern clues in the wording

  • → Largest square of ones

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int maximalSquare(char[][] matrix) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
4
2
matrix = [["0","1"],["1","0"]]
1
3
matrix = [["0"]]
0

From slow to fast

Approaches

1. Side-length DP · O(m × n)
1

Side-length DP

Time O(m × n) Space O(m × n)

Pad with a zero row and column; dp[r + 1][c + 1] from the three neighbours; track the largest side.

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

Verdict: Classic.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No ones (0)
  • All ones

Mistakes people make

  • Returning the side instead of the area.

Interview

Follow-up questions

What about the largest rectangle of ones?