Find the Largest Area of Square Inside Two Rectangles

Medium

There exist n rectangles in a 2D plane with edges parallel to the x and y axis. You receive 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^th rectangle, respectively.

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

Example 1

Original illustrative diagram 1 for Find the Largest Area of Square Inside Two Rectangles

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

Original illustrative diagram 2 for Find the Largest Area of Square Inside Two Rectangles

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

Original illustrative diagram 3 for Find the Largest Area of Square Inside Two Rectangles

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

Original illustrative diagram 4 for Find the Largest Area of Square Inside Two Rectangles

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]

Did this problem appear in one of your interviews?

Responses stay private.

Constraints

Did this problem appear in one of your interviews?

Acceptance rate: 0%