Is Find the Largest Area of Square Inside Two Rectangles easy or hard?

This problem is rated Medium. The geometry for rectangle intersection is straightforward, but recognizing that the square size is limited by the smaller overlap dimension and handling all rectangle pairs correctly requires careful implementation.

Find the Largest Area of Square Inside Two Rectangles Python/Java solution

Python and Java implementations typically compute intersections using coordinate math: left = max(x1a, x1b), right = min(x2a, x2b), bottom = max(y1a, y1b), and top = min(y2a, y2b). If the overlap exists, the square side equals min(right - left, top - bottom) and the area is side^2.

How to solve Find the Largest Area of Square Inside Two Rectangles in O(n)?

Achieving strict O(n) time is generally not feasible because rectangle intersections depend on pair relationships. The closest optimization is a sweep line algorithm with sorting, which runs in O(n log n). It processes rectangles in coordinate order and only checks overlaps among active rectangles.

What is the best approach for Find the Largest Area of Square Inside Two Rectangles?

The most practical approach is pair-wise rectangle intersection checking. For each pair, compute the overlapping region and take the square side as min(overlap width, overlap height). This runs in O(n^2) time and O(1) space and is usually sufficient for interview constraints. For larger inputs, a sweep line technique can reduce unnecessary comparisons.

Is Find the Largest Area of Square Inside Two Rectangles asked at Google/Amazon/Meta?

Problems involving rectangle intersections and sweep line algorithms frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include rectangle overlap detection, skyline problems, and computing intersection areas using geometry or interval sweeps.

What data structure is used in Find the Largest Area of Square Inside Two Rectangles?

The brute force method mainly uses arrays and simple coordinate comparisons. The optimized sweep line approach uses sorted event lists and an active set structure, often implemented with balanced trees or interval lists to track overlapping rectangles during the sweep.

What is the time complexity of Find the Largest Area of Square Inside Two Rectangles?

The straightforward solution checks every pair of rectangles, giving O(n^2) time complexity and O(1) extra space. A sweep line optimization sorts rectangle edges and processes overlaps in roughly O(n log n + k) time, where k is the number of candidate overlaps considered.

Description Hints 3 Solution Video 33:46

3047. Find the Largest Area of Square Inside Two Rectangles

Medium66.9% acceptance5 companies

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^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. 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]

Asked at 5 companies

Cisco

Google Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Brute Force the intersection area of each pair of rectangles.

Hint 2

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.

Hint 3

The intersection area (if any) is also a rectangle. Find its corners.

33:46

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

3047. Find the Largest Area of Square Inside Two Rectangles

Asked at 5 companies

Topics

Hints open one at a time

Similar problems