LeetCode 3047 - Find the Largest Area of Square Inside Two Rectangles

The problem asks us to find the largest square that can fit inside the overlapping region of at least two rectangles on a 2D plane. Each rectangle is axis-aligned, meaning its sides are parallel to the x-axis and y-axis.

leetcodemediumarraymathgeometry

LeetCode Problem 3047

Difficulty: 🟡 Medium
Topics: Array, Math, Geometry

Solution

Problem Understanding

The problem asks us to find the largest square that can fit inside the overlapping region of at least two rectangles on a 2D plane. Each rectangle is axis-aligned, meaning its sides are parallel to the x-axis and y-axis. The rectangles are defined by their bottom-left and top-right coordinates, which are given as integer pairs in two separate lists, bottomLeft and topRight.

The task is not just to find any square inside a rectangle but specifically a square that lies entirely within the intersection of at least two rectangles. If no two rectangles intersect, the maximum square area should be 0.

Constraints tell us that there can be up to 103 rectangles, and the coordinates themselves can be very large (up to 10^7). Each rectangle has positive area, as guaranteed by bottomLeft[i][0] < topRight[i][0] and bottomLeft[i][1] < topRight[i][1].

Important edge cases include:

  • Rectangles that do not intersect at all, which should return 0.
  • Rectangles that intersect in a line or point but cannot contain a square.
  • Rectangles that intersect in large areas, potentially forming a square of maximum size.

Approaches

Brute Force

The brute-force approach considers every pair of rectangles and computes their intersection. Once we have the intersection coordinates, we calculate the largest square that can fit inside the intersection. The side length of the square is limited by the smaller of the width and height of the intersection. We repeat this for all pairs and track the maximum square area.

This approach works correctly but is potentially slow, since it checks all n * (n-1) / 2 pairs, which is about 500,000 operations at worst for n = 103. While feasible for n = 103, it is not optimal and has redundant computations.

Optimal Insight

The key observation is that for any set of rectangles, the intersection of at least two rectangles will be bounded by the maximum of the lower x-coordinates, maximum of lower y-coordinates, minimum of upper x-coordinates, and minimum of upper y-coordinates. Since we are only concerned with pairs of rectangles, we can efficiently iterate over all pairs, calculate the intersection, and find the largest possible square inside each intersection.

This ensures that we do not miss any potential candidate while avoiding unnecessary computation beyond pairs. Further optimization might involve spatial sorting or line sweeping, but for n ≤ 103, the pairwise approach is both simple and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check every pair of rectangles and compute intersection
Optimal O(n^2) O(1) Pairwise intersection computation with direct square side calculation

Algorithm Walkthrough

  1. Initialize a variable max_side to 0. This will store the side length of the largest square found.
  2. Iterate over all pairs of rectangles (i, j) where i < j.
  3. For each pair, compute the intersection coordinates:
  • inter_left = max(bottomLeft[i][0], bottomLeft[j][0])
  • inter_bottom = max(bottomLeft[i][1], bottomLeft[j][1])
  • inter_right = min(topRight[i][0], topRight[j][0])
  • inter_top = min(topRight[i][1], topRight[j][1])
  1. Check if the intersection is valid, i.e., inter_left < inter_right and inter_bottom < inter_top.
  2. If valid, compute the width and height of the intersection: width = inter_right - inter_left, height = inter_top - inter_bottom.
  3. The largest square that can fit has a side length side = min(width, height).
  4. Update max_side if side is greater than the current value.
  5. After iterating all pairs, return max_side * max_side as the area of the largest square.

Why it works: For every intersecting region of at least two rectangles, we compute the maximal square that can fit. By checking all pairs, we ensure that all possible intersection regions are considered. The min(width, height) ensures the square fits within the bounds.

Python Solution

from typing import List

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        n = len(bottomLeft)
        max_side = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                inter_left = max(bottomLeft[i][0], bottomLeft[j][0])
                inter_bottom = max(bottomLeft[i][1], bottomLeft[j][1])
                inter_right = min(topRight[i][0], topRight[j][0])
                inter_top = min(topRight[i][1], topRight[j][1])
                
                if inter_left < inter_right and inter_bottom < inter_top:
                    width = inter_right - inter_left
                    height = inter_top - inter_bottom
                    side = min(width, height)
                    max_side = max(max_side, side)
        
        return max_side * max_side

The Python implementation directly follows the algorithm steps. It uses nested loops for pairs, calculates the intersection region, and determines the maximal square that can fit. Using max and min ensures correct bounds. The final result multiplies the side length by itself to return the area.

Go Solution

func largestSquareArea(bottomLeft [][]int, topRight [][]int) int64 {
    n := len(bottomLeft)
    var maxSide int64 = 0
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            interLeft := max(bottomLeft[i][0], bottomLeft[j][0])
            interBottom := max(bottomLeft[i][1], bottomLeft[j][1])
            interRight := min(topRight[i][0], topRight[j][0])
            interTop := min(topRight[i][1], topRight[j][1])
            
            if interLeft < interRight && interBottom < interTop {
                width := int64(interRight - interLeft)
                height := int64(interTop - interBottom)
                side := minInt64(width, height)
                if side > maxSide {
                    maxSide = side
                }
            }
        }
    }
    
    return maxSide * maxSide
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func minInt64(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

The Go solution mirrors the Python logic. All arithmetic uses int64 to prevent overflow when squaring large coordinates. Helper functions for min and max simplify code readability.

Worked Examples

Example 1

Input: bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]

  • Pair (0,1) intersection: [2,2] to [3,3], width = 1, height = 1 → side = 1 → max_side = 1
  • Pair (0,2) intersection: [3,1] to [3,3] → invalid
  • Pair (1,2) intersection: [3,2] to [4,4] → width = 1, height = 2 → side = 1 → max_side = 1

Output: 1 * 1 = 1

Example 2

Input: bottomLeft = [[1,1],[1,3],[1,5]], topRight = [[5,5],[5,7],[5,9]]

  • Pair (0,1): [1,3] to [5,5] → width = 4, height = 2 → side = 2 → max_side = 2
  • Pair (1,2): [1,5] to [5,7] → width = 4, height = 2 → side = 2 → max_side = 2

Output: 2 * 2 = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We iterate over all pairs of rectangles to compute intersections
Space O(1) Only a few variables are used for intersections and max_side

The solution is efficient for n up to 103. Memory usage is minimal since we do not store intermediate results.

Test Cases

# provided examples
assert Solution().largestSquareArea([[1,1],[2,2],[3,1]], [[3,3],[4,4],[6,6]]) == 1  # Example 1
assert Solution().largestSquareArea([[1,1],[1,3],[1,5]], [[5,5],[5,7],[5,9]]) == 4  # Example 2
assert Solution().largestSquareArea([[1,1],[2,2],[1,2]], [[3,3],[4,4],[3,4]]) == 1  # Example 3
assert Solution().largestSquareArea([[1,1],[3,