0943MediumArrayBinary SearchDynamic ProgrammingMatrix

Two Equal Squares of Sound Panel

Tracked in this browser only

Trains the technique from

LeetCode 4016Maximum Area of Two Non-Overlapping Square Submatrices

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A panel is given as mat, each cell holding 0 or 1. A cell holding 1 is sound.

Find two squares of sound cells, both the same size, that do not overlap each other, choosing the largest size for which two such squares exist. Return the total area they cover, which is twice the square of that size, or 0 when no two squares of any size fit.

Examples

Example 1

Input: mat = [[1, 1, 1, 1], [1, 1, 1, 1]]
Output: 8

Two squares of side two fit side by side in the four columns without overlapping, covering eight cells between them. No larger size fits at all on a panel two rows deep.

Example 2

Input: mat = [[1, 1]]
Output: 2

Two single sound cells sit apart from each other, covering two cells.

Example 3

Input: mat = [[1]]
Output: 0

There is only one sound cell, so no two squares fit.

Constraints

1 <= mat.length <= 500
1 <= mat[i].length <= 500
Every row of mat has the same length
mat[i][j] is either 0 or 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_area(mat: list[list[int]]) -> int:

Java

public int maxArea(int[][] mat)

The intended approach

Time O(m * n log(min(m, n))) for an m by n panel.Space O(m * n) for the square sizes per cell.

First work out, for every cell, the largest square of sound cells whose bottom-right corner sits there. That comes from one sweep: a sound cell extends the smallest of the three squares ending above, to the left, and up-left, by one. Then note that two squares that do not overlap can always be separated by a straight line, across or down, because two rectangles that overlap in both directions must share a cell. So testing whether two squares of a given size fit is a matter of asking, for each cut, whether one fits wholly on each side. Running totals of the earliest and latest rows and columns where a square of that size can sit answer every cut in one pass. Two squares of a given size fitting means two of any smaller size fit as well, so the largest workable size can be found by halving the range rather than trying each.

Pythonentry point: max_area

def max_area(mat):
    m = len(mat)
    n = len(mat[0])
    side = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            if mat[r][c] == 0:
                continue
            if r == 0 or c == 0:
                side[r][c] = 1
            else:
                up = side[r - 1][c]
                left = side[r][c - 1]
                corner = side[r - 1][c - 1]
                smallest = up if up < left else left
                if corner < smallest:
                    smallest = corner
                side[r][c] = smallest + 1

    def two_fit(want):
        # rows and columns, as bottom-right corners, where a square of this size sits
        rows = []
        cols = []
        for r in range(m):
            for c in range(n):
                if side[r][c] >= want:
                    rows.append(r)
                    cols.append(c)
        if len(rows) < 2:
            return len(rows) >= 2
        # a cut across: some square ends at or above one row, another starts below it
        top_first = None
        top_last = None
        left_first = None
        left_last = None
        for r in range(m):
            for c in range(n):
                if side[r][c] < want:
                    continue
                if top_first is None or r < top_first:
                    top_first = r
                if top_last is None or r > top_last:
                    top_last = r
                if left_first is None or c < left_first:
                    left_first = c
                if left_last is None or c > left_last:
                    left_last = c
        if top_first is None:
            return False
        if top_last - top_first >= want:
            return True
        if left_last - left_first >= want:
            return True
        return False

    low = 1
    high = m if m < n else n
    best = 0
    while low <= high:
        mid = (low + high) // 2
        if two_fit(mid):
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    return 2 * best * best

The obvious version

Take every pair of squares of the same size anywhere on the panel, check both are all sound and that they do not overlap, and keep the largest size that works. Quartic in the panel's side lengths and it reasons about nothing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_area(mat):
    m = len(mat)
    n = len(mat[0])

    def sound(r, c, size):
        if r + size > m or c + size > n:
            return False
        for i in range(r, r + size):
            for j in range(c, c + size):
                if mat[i][j] == 0:
                    return False
        return True

    best = 0
    top = m if m < n else n
    for size in range(1, top + 1):
        spots = []
        for r in range(m - size + 1):
            for c in range(n - size + 1):
                if sound(r, c, size):
                    spots.append((r, c))
        found = False
        for a in range(len(spots)):
            for b in range(a + 1, len(spots)):
                r1, c1 = spots[a]
                r2, c2 = spots[b]
                rows_apart = r1 + size <= r2 or r2 + size <= r1
                cols_apart = c1 + size <= c2 or c2 + size <= c1
                if rows_apart or cols_apart:
                    found = True
                    break
            if found:
                break
        if found:
            best = size
    return 2 * best * best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in