Skip to content

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.

Medium#3047
LeetCode Problem

Find the Largest Area of Square Inside Two Rectangles

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

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^3
bottomLeft[i].length == topRight[i].length == 2
1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10^7
1 <= topRight[i][0], topRight[i][1] <= 10^7
bottomLeft[i][0] < topRight[i][0]
bottomLeft[i][1] < topRight[i][1]

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.