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.

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.

Description Hints 3 Solution Video 22:02

4016. Maximum Area of Two Non-Overlapping Square Submatrices

Q: 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.

Q: 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.

Medium40.9% acceptance

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.

Topics

Hints open one at a time

Hint 1

Binary search for the maximum side length k. If two valid squares of side length k exist, two valid squares of every smaller side length also exist.

Hint 2

Build a 2D prefix sum so that you can determine in constant time whether every cell in a given square is usable.

Hint 3

For a fixed k, record the minimum and maximum row and column among the top-left corners of all valid squares. Two of them can be disjoint if the difference between the maximum and minimum row is at least k, or the corresponding column difference is at least k.

22:02

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxArea(self, mat: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,1,1,0],[1,1,1,1],[0,0,1,1]]

Input

[[0,1],[1,0]]

Input

[[0,0],[0,1]]

Your code is saved on this device.Solution