Maximal square matrix

Find the largest square of 1s in a binary matrix using dynamic programming.

dynamic-programming matrix maximum-square 2d-array

Write a function `maximal_square(matrix)` that takes a non-empty rectangular 2D list of integers (each element is 0 or 1) and returns the side length of the largest square submatrix that contains only 1s. If there are no 1s, return 0.

A square submatrix is a contiguous block of cells with equal number of rows and columns. The function should be efficient enough for matrices up to 300x300.

Constraints

- `1 <= len(matrix) <= 300`
- `1 <= len(matrix[0]) <= 300`
- Each element is exactly `0` or `1`.
- Time complexity O(R*C), space O(C) or O(R*C).

Example

>>> maximal_square([[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]])
2
>>> maximal_square([[0,0],[0,0]])
0
>>> maximal_square([[1]])
1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Let dp[i][j] be the side length of the largest square with bottom-right corner at (i,j).

If matrix[i][j] == 1, then dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Track the maximum dp value as you fill the table.

You can reduce space to one row by updating dp from left to right and keeping a previous diagonal value.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.