3047. Find the Largest Area of Square Inside Two Rectangles

Array
Math
Geometry

TIME

O(n²)

SPACE

O(1)

Intuition

For each pair of rectangles, compute their intersection. If the intersection exists, the largest square that fits inside it has a side length equal to the minimum of the intersection's width and height.

Solution

Iterate all pairs: Check every pair of rectangles (i, j) where i < j.
Compute intersection: For rectangles A and B:
- left = max(A.x1, B.x1)
- right = min(A.x2, B.x2)
- bottom = max(A.y1, B.y1)
- top = min(A.y2, B.y2)
Check validity: Intersection exists if right > left and top > bottom.
Compute max square side: If intersection exists, the largest square side is min(right - left, top - bottom).
Track maximum: Keep the maximum side across all pairs.
Return area: Return maxSide * maxSide.

Complexity

Time: O(n²), checking all pairs of rectangles
Space: O(1), only storing max side

Edge Cases

No rectangles intersect → return 0
Intersection is a line (width or height is 0) → no square fits
Multiple pairs have same max square → any valid answer works

Code

from typing import List


class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        """
        3047. Find the Largest Area of Square Inside Two Rectangles
        Time: O(n²)
        Space: O(1)
        """
        n = len(bottomLeft)
        max_side = 0

        for i in range(n):
            ax1, ay1 = bottomLeft[i]
            ax2, ay2 = topRight[i]

            for j in range(i + 1, n):
                bx1, by1 = bottomLeft[j]
                bx2, by2 = topRight[j]

                left = max(ax1, bx1)
                right = min(ax2, bx2)
                bottom = max(ay1, by1)
                top = min(ay2, by2)

                if right > left and top > bottom:
                    side = min(right - left, top - bottom)
                    max_side = max(max_side, side)

        return max_side * max_side

/**
 * 3047. Find the Largest Area of Square Inside Two Rectangles
 * Time: O(n²)
 * Space: O(1)
 */
class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int n = bottomLeft.length;
        long maxSide = 0;

        for (int i = 0; i < n; i++) {
            int ax1 = bottomLeft[i][0];
            int ay1 = bottomLeft[i][1];
            int ax2 = topRight[i][0];
            int ay2 = topRight[i][1];

            for (int j = i + 1; j < n; j++) {
                int bx1 = bottomLeft[j][0];
                int by1 = bottomLeft[j][1];
                int bx2 = topRight[j][0];
                int by2 = topRight[j][1];

                int left = Math.max(ax1, bx1);
                int right = Math.min(ax2, bx2);
                int bottom = Math.max(ay1, by1);
                int top = Math.min(ay2, by2);

                if (right > left && top > bottom) {
                    long side = Math.min(right - left, top - bottom);
                    maxSide = Math.max(maxSide, side);
                }
            }
        }

        return maxSide * maxSide;
    }
}