Show problems as
Classic problem #4016MediumArrayBinary SearchDynamic ProgrammingMatrix

Maximum Area of Two Non-Overlapping Square Submatrices

Real-world version: Two Equal Squares of Sound Panel
Tracked in this browser only
Read Maximum Area of Two Non-Overlapping Square Submatrices on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A panel is given as mat, each cell holding 0 or 1. A cell holding 1 is sound.

Find two squares of sound cells, both the same size, that do not overlap each other, choosing the largest size for which two such squares exist. Return the total area they cover, which is twice the square of that size, or 0 when no two squares of any size fit.

Examples

Example 1

Input
mat = [[1, 1, 1, 1], [1, 1, 1, 1]]
Output
8

Two squares of side two fit side by side in the four columns without overlapping, covering eight cells between them. No larger size fits at all on a panel two rows deep.

Example 2

Input
mat = [[1, 1]]
Output
2

Two single sound cells sit apart from each other, covering two cells.

Example 3

Input
mat = [[1]]
Output
0

There is only one sound cell, so no two squares fit.

Constraints

  • 1 <= mat.length <= 500
  • 1 <= mat[i].length <= 500
  • Every row of mat has the same length
  • mat[i][j] is either 0 or 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_area(mat: list[list[int]]) -> int:
Java
public int maxArea(int[][] mat)

More on the same topics