Skip to main content
Talentd

Maximum Area of Two Non-Overlapping Square Submatrices - Solution & Explanation

MediumArrayBinary SearchDynamic ProgrammingMatrix16 min read
Practice this problem

Problem Statement

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:

  • 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 == m
  • mat[i].length == n
  • 1 <= m, n <= 500
  • mat[i][j] is either 0 or 1.

Approach Overview

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

Solution

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):

  • Bottom-up dynamic programming: let 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).
  • Top-down dynamic programming: let 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).
  • Enumerate the dividing line 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^4)O(1)Small matrices or verification
DP + Dividing LinesO(n^2)O(n^2)General case (optimal)

Video Solution

LeetCode: Maximum Area of Two Non-Overlapping Square Submatrices (Weekly Contest 514) | Solution Q3 • AlgoTribe • 1,678 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Area of Two Non-Overlapping Square Submatrices easy or hard?
It's rated Medium on FleetCode with a 39.6% acceptance rate. The brute force is easy but inefficient; the optimal DP solution requires careful insight about dividing lines and prefix/suffix aggregation.
Maximum Area of Two Non-Overlapping Square Submatrices Python solution?
In Python, implement dp with a list of lists, use nested loops for transitions, then compute prefix/suffix maximums with similar loops. The final answer is max over all cuts of best_left + best_right.
How to solve Maximum Area of Two Non-Overlapping Square Submatrices in O(n^2)?
First, compute dp[i][j] = side length of largest all-ones square ending at (i,j). Then build best_left and best_right arrays using prefix maximums. Finally, enumerate all horizontal and vertical cuts, combining the best square from each side to maximize the sum.
What is the best approach for Maximum Area of Two Non-Overlapping Square Submatrices?
The optimal approach uses dynamic programming to compute the largest all-ones square ending at each cell, then builds prefix/suffix maximums to find the best square on each side of every horizontal and vertical dividing line. This runs in O(n^2) time and O(n^2) space.
Is Maximum Area of Two Non-Overlapping Square Submatrices asked at Google/Amazon/Meta?
This problem tests DP and matrix manipulation skills commonly evaluated at top tech companies. While not a classic interview question, its pattern appears in variants like Maximal Square and is useful for Google and Meta interviews.
What data structure is used in Maximum Area of Two Non-Overlapping Square Submatrices?
The solution primarily uses a 2D DP array to store square sizes and additional 2D arrays for prefix/suffix maximums. No complex data structures are needed beyond standard arrays.
What is the time complexity of Maximum Area of Two Non-Overlapping Square Submatrices?
The optimal solution runs in O(n^2) time for an n x n matrix, where n is the number of rows or columns. Space complexity is also O(n^2) due to the DP table and auxiliary arrays.

Ready to solve this problem?

Practice Maximum Area of Two Non-Overlapping Square Submatrices with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays