3047. Find the Largest Area of Square Inside Two Rectangles

#php #leetcode #algorithms #programming

Difficulty: Medium

Topics: Array, Math, Geometry, Weekly Contest 386

There exist n rectangles in a 2D plane with edges parallel to the x and y axis. You are given two 2D integer arrays bottomLeft and topRight where bottomLeft[i] = [a_i, b_i] and topRight[i] = [c_i, d_i] represent the bottom-left and top-right coordinates of the iᵗʰ rectangle, respectively.

You need to find the maximum area of a square that can fit inside the intersecting region of at least two rectangles. Return 0 if such a square does not exist.

Example 1:

Input: bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
Output: 1
Explanation: A square with side length 1 can fit inside either the intersecting region of rectangles 0 and 1 or the intersecting region of rectangles 1 and 2. Hence the maximum area is 1. It can be shown that a square with a greater side length can not fit inside any intersecting region of two rectangles.

Example 2:

Input: bottomLeft = [[1,1],[1,3],[1,5]], topRight = [[5,5],[5,7],[5,9]]
Output: 4
Explanation: A square with side length 2 can fit inside either the intersecting region of rectangles 0 and 1 or the intersecting region of rectangles 1 and 2. Hence the maximum area is 2 * 2 = 4. It can be shown that a square with a greater side length can not fit inside any intersecting region of two rectangles.

Example 3:

Input: bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
Output: 1
Explanation: A square with side length 1 can fit inside the intersecting region of any two rectangles. Also, no larger square can, so the maximum area is 1. Note that the region can be formed by the intersection of more than 2 rectangles.

Example 4:

Input: bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
Output: 0
Explanation: No pair of rectangles intersect, hence, the answer is 0.

Constraints:

n == bottomLeft.length == topRight.length
2 <= n <= 10³
bottomLeft[i].length == topRight[i].length == 2
1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10⁷
1 <= topRight[i][0], topRight[i][1] <= 10⁷
bottomLeft[i][0] < topRight[i][0]
bottomLeft[i][1] < topRight[i][1]

Hint:

Brute Force the intersection area of each pair of rectangles.
Two rectangles will not overlap when the bottom left x coordinate of one rectangle is greater than the top right x coordinate of the other rectangle. The same is true for the y coordinate.
The intersection area (if any) is also a rectangle. Find its corners.

Solution:

We need to find the largest square that fits inside the intersection region of at least two rectangles. Let me break down the solution approach and then provide the implementation.

Approach:

Iterate through every pair of rectangles (i, j) where i < j
Calculate their intersection region using:
- max(bottomLeft[i][0], bottomLeft[j][0]) for left x
- min(topRight[i][0], topRight[j][0]) for right x
- max(bottomLeft[i][1], bottomLeft[j][1]) for bottom y
- min(topRight[i][1], topRight[j][1]) for top y
If left < right AND bottom < top, rectangles intersect
The intersection forms a rectangle; the largest square inside has side length = min(width, height)
Track the maximum square area across all intersecting pairs
Return 0 if no intersections found

Let's implement this solution in PHP: 3047. Find the Largest Area of Square Inside Two Rectangles

<?php
/**
 * @param Integer[][] $bottomLeft
 * @param Integer[][] $topRight
 * @return Integer
 */
function largestSquareArea(array $bottomLeft, array $topRight): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo largestSquareArea([[1,1],[2,2],[3,1]], [[3,3],[4,4],[6,6]]) . "\n";            // Output: 1
echo largestSquareArea([[1,1],[1,3],[1,5]], [[5,5],[5,7],[5,9]]) . "\n";            // Output: 4
echo largestSquareArea([[1,1],[2,2],[1,2]], [[3,3],[4,4],[3,4]]) . "\n";            // Output: 1
echo largestSquareArea([[1,1],[3,3],[3,1]], [[2,2],[4,4],[4,2]]) . "\n";            // Output: 0
?>

Explanation:

Pairwise Checking: We check all rectangle pairs because the problem requires intersection of at least two rectangles. If more than two rectangles intersect, their common intersection area is contained within each pair's intersection area.
Intersection Logic: Two rectangles intersect if their x-ranges and y-ranges overlap. The intersection region is defined by the overlap of both ranges.
Square Constraint: A square requires equal width and height. The largest square fitting in a rectangle uses the smaller dimension as the side length.
Complexity: O(n²) time, O(1) extra space, which is acceptable for n ≤ 1000.

Complexity

Time Complexity: O(n²), where n is the number of rectangles
- We check all pairs of rectangles, which is n*(n-1)/2 pairs
- For each pair, we perform constant-time operations
Space Complexity: O(1)
- We only use a constant amount of extra space

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!