Practice/Google/Leetcode 3047. Find the Largest Area of Square Inside Two Rectangles

Leetcode 3047. Find the Largest Area of Square Inside Two Rectangles

CodingOptional

Problem

You are given an array of rectangles where each rectangle is represented as [x1, y1, x2, y2]. Each rectangle is axis-aligned with its bottom-left corner at (x1, y1) and its top-right corner at (x2, y2).

Your task is to find the largest possible square that can fit entirely within the intersection area of at least two rectangles. Return the area of this largest square, or 0 if no two rectangles overlap.

Requirements

1. Calculate the intersection region for every pair of rectangles
2. For each valid intersection, determine the largest square that can fit inside it
3. Return the maximum square area found across all intersections
4. If no rectangles intersect, return 0

Constraints

• 1 <= rectangles.length <= 100
• rectangles[i].length == 4
• 0 <= x1 < x2 <= 10^9
• 0 <= y1 < y2 <= 10^9
• All coordinates are integers

Examples

Example 1:

Input: rectangles = [[1,1,3,3],[2,2,4,4]] Output: 1 Explanation: The rectangles intersect in region [2,2,3,3]. This intersection has width 1 and height 1, so the largest square has side length 1 and area 1.

Example 2:

Input: rectangles = [[1,1,5,5],[2,2,6,6],[3,3,7,7]] Output: 9 Explanation: The first two rectangles intersect at [2,2,5,5] (width=3, height=3, area=9). The first and third intersect at [3,3,5,5] (width=2, height=2, area=4). The second and third intersect at [3,3,6,6] (width=3, height=3, area=9). Maximum is 9.

Example 3:

Input: rectangles = [[1,1,2,2],[3,3,4,4]] Output: 0 Explanation: The rectangles do not overlap, so there is no intersection and the answer is 0.