Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A square lying inside two rectangles must lie inside their intersection. That intersection is itself an axis-aligned rectangle, so its largest possible square has side length equal to the smaller of its width and height.

Approach

Examine every unordered pair of rectangles. First check that their horizontal and vertical ranges overlap with positive length; touching edges or corners cannot contain a positive-area square.

For an overlapping pair, compute the intersection's left and bottom boundaries as the larger corresponding lower bounds, and its right and top boundaries as the smaller upper bounds. Its width is right - left and its height is top - bottom. Square their minimum and update the maximum area. Return zero if no pair has a positive-area intersection. Any square covered by at least two rectangles is covered by some examined pair, so considering pairs is sufficient.

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        n = len(bottomLeft)
        res = 0

        for i in range(n):
            for j in range(i + 1, n):
                xl1, yb1 = bottomLeft[i]
                xr1, yt1 = topRight[i]
                xl2, yb2 = bottomLeft[j]
                xr2, yt2 = topRight[j]
                if (xl2 < xr1 and xl1 < xr2) and (yb2 < yt1 and yb1 < yt2):
                    l = max(xl1, xl2)
                    r = min(xr1, xr2)
                    t = min(yt1, yt2)
                    b = max(yb1, yb2)
                    res = max(res, min(r - l, t - b) ** 2)

        return res

Complexity analysis

Let n be the number of rectangles. Time: O(n^2). Auxiliary space: O(1).