You are given a 2D integer matrix mat of size m × n, where:
mat[r][c] == 1means the cell at rowrand columncis usable.mat[r][c] == 0means it is not usable.
Your task is to find two that satisfy the following conditions:
- Both submatrices must be squares of the same side length
k. - The two submatrices must not share any cell.
- Each submatrix can only cover cells where
mat[r][c] == 1.
Return the maximum possible area of each of the two squares. If it is not possible to choose two such squares, return 0.
Example 1:
Input: mat = [[1,1,1,0],[1,1,1,1],[0,0,1,1]]
Output: 4
Explanation:
The largest equal non-overlapping squares have side length k = 2 with area 4.
- First square starts at top-left
(0, 0)and covers cells(0, 0),(0, 1),(1, 0), and(1, 1). - Second square starts at top-left
(1, 2)and covers cells(1, 2),(1, 3),(2, 2), and(2, 3).
Thus, the answer is 4.
Example 2:
Input: mat = [[0,1],[1,0]]
Output: 1
Explanation:
The largest equal non-overlapping squares have side length k = 1 with area 1.
- First square starts at top-left
(0, 1)and covers cell(0, 1). - Second square starts at top-left
(1, 0)and covers cell(1, 0).
Thus, the answer is 1.
Example 3:
Input: mat = [[0,0],[0,1]]
Output: 0
Explanation:
There is only one usable cell, so it is impossible to choose two non-overlapping squares. Thus, the answer is 0.
Constraints:
mat.length == mmat[i].length == n1 <= m, n <= 500mat[i][j]is either 0 or 1.