Maximal square

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

dynamic-programming matrix maximal-square 2d-array

Write a function `maximal_square(matrix)` that takes a non-empty 2D list of integers (each either 0 or 1) and returns the area of the largest square sub-matrix that contains only 1s. If there are no 1s, return 0. The matrix dimensions are at most 300×300.

Your solution must solve the problem in O(rows * cols) time and O(rows * cols) space. You may assume that the input matrix is a valid rectangular list of lists.

Implement the function with the exact signature:

```python
def maximal_square(matrix):
    ...
```

**Input:** A list of lists of integers, e.g., `[[1, 0, 1], [1, 1, 0], [1, 1, 1]]`.

**Output:** An integer representing the area (number of cells) of the largest square of 1s.

**Examples:**
- `maximal_square([[1, 0, 1], [1, 1, 0], [1, 1, 1]])` returns `4` (the 2×2 square at the bottom left).
- `maximal_square([[0, 0], [0, 0]])` returns `0`.
- `maximal_square([[1]])` returns `1`.
- `maximal_square([[1, 1], [1, 1]])` returns `4`.

Constraints

1 ≤ rows, cols ≤ 300. Each element is either 0 or 1. Time complexity: O(rows * cols). Space complexity: O(rows * cols) (or O(cols) if desired, but O(rows*cols) is acceptable).

Example

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

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a DP table where dp[i][j] represents the side length of the largest square whose bottom-right corner is at cell (i, j).

For a cell with value 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. For 0 it stays 0.

Track the maximum side length seen, then return its square.

Be careful with the first row and first column only having 1s as possible side length 1 squares.

Test Results

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