You are given a 2D integer matrix mat of size m × n, where:
mat[r][c] == 1 means the cell at row r and column c is usable.mat[r][c] == 0 means it is not usable.Your task is to find two submatrices that satisfy the following conditions:
k.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.
(0, 0) and covers cells (0, 0), (0, 1), (1, 0), and (1, 1).(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.
(0, 1) and covers cell (0, 1).(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.Problem Overview: You are given a binary matrix (each cell is 0 or 1) and need to find two square submatrices that do not overlap, each containing only 1s, such that the sum of their areas is maximized. The squares can be of any size, but they must be disjoint (no shared cells).
Approach 1: Brute Force (O(n^4) time, O(1) space)
Enumerate every possible square submatrix by checking all top-left corners and all possible side lengths. For each square, verify all cells are 1s using a nested loop. Then, for every pair of squares, check if they overlap by comparing row and column intervals. This approach is straightforward but impractical for matrices larger than 50x50. It demonstrates the problem's core requirements but fails on performance.
Approach 2: Dynamic Programming + Enumerating Dividing Lines (O(n^2) time, O(n^2) space)
This is the optimal approach. First, precompute a DP table dp[i][j] that stores the side length of the largest all-ones square whose bottom-right corner is at (i, j). The recurrence is dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == 1, else 0. Then, compute two auxiliary arrays: best_left[i][j] = maximum side length of any square fully contained in the submatrix from rows 0..i and columns 0..j, and best_right[i][j] = maximum side length in the submatrix from rows i..n-1 and columns j..m-1. These are built using prefix maximums over the DP table. Finally, enumerate all possible dividing lines: either a horizontal cut between rows i and i+1 (combining best from top and bottom) or a vertical cut between columns j and j+1 (combining best from left and right). For each cut, the answer is the sum of the two best squares on opposite sides. The maximum over all cuts gives the result.
The key insight is that two non-overlapping squares can always be separated by a straight horizontal or vertical line. This allows you to reduce the problem to finding the best square on each side of every possible dividing line. The DP table gives you the largest square ending at each cell, and prefix/suffix maximums let you answer
Two non-overlapping axis-aligned rectangles can always be separated by a horizontal line or a vertical line (their row intervals or column intervals must be disjoint). Therefore, we only need to consider the case where one square lies entirely above some horizontal dividing line and the other below it, and the case where one lies entirely to the left of some vertical dividing line and the other to its right. The latter can be handled by transposing the matrix and reusing the logic of the former.
For the horizontal case, we design a function calc(mat):
f[i][j] be the maximum side length of an all-1 square with top-left corner at (i, j). If mat[i][j] = 1, then f[i][j] = min(f[i+1][j], f[i][j+1], f[i+1][j+1]) + 1. We use g[i] to record the maximum side length in row i, then compute the suffix maximum suf[i] = max(suf[i+1], g[i]), which represents the maximum side length of an all-1 square within rows [i, m).f[i][j] be the maximum side length of an all-1 square with bottom-right corner at (i-1, j-1). If mat[i-1][j-1] = 1, then f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1. Similarly, we compute the prefix maximum pre[i] = max(pre[i-1], g[i]), which represents the maximum side length of an all-1 square within rows [0, i).i \in [1, m) between every pair of adjacent rows. The maximum side length of an all-1 square above the line is pre[i], and below it is suf[i]. Since the two squares must have equal side lengths, the feasible side length is t = min(pre[i], suf[i]), and we update the answer with t^2.Finally, return max(calc(mat), calc(mat^\top)).
The time complexity is O(m times n), and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^4) | O(1) | Small matrices or verification |
| DP + Dividing Lines | O(n^2) | O(n^2) | General case (optimal) |
LeetCode: Maximum Area of Two Non-Overlapping Square Submatrices (Weekly Contest 514) | Solution Q3 • AlgoTribe • 1,678 views views
Watch 7 more video solutions →Practice Maximum Area of Two Non-Overlapping Square Submatrices with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor