Practice Find the Largest Area of Square Inside Two Rectangles
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Rectangles are axis-aligned, with opposite corners given by corresponding entries of bottomLeft and topRight. Find the largest area of a square contained in a region shared by at least two rectangles. Return zero when no such square has positive area. Practice approach: Check each pair. Its overlap width is min(right edges) - max(left edges), and its overlap height is min(top edges) - max(bottom edges). If both are positive, the largest fitting square has side min(width, height). Maximize the squared side using a wide integer. Pairwise checks suffice even for a region shared by more rectangles, and cost O(n^2) time with O(1) extra space.
Source: Find the Largest Area of Square Inside Two Rectangles on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
1
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
bottomLeft = [[1,1],[1,3],[1,5]], topRight = [[5,5],[5,7],[5,9]]
4
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
bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
1
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
bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
0
No pair of rectangles intersect, hence, the answer is 0.
Constraints
Related LeetCode Problems
Practice more problems similar to Find the Largest Area of Square Inside Two Rectangles.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.