Watch 8 video solutions for Maximum Area of Two Non-Overlapping Square Submatrices, a medium level problem. This walkthrough by AlgoTribe has 1,678 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
| 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) |