Watch 10 video solutions for Find the Largest Area of Square Inside Two Rectangles, a medium level problem involving Array, Math, Geometry. This walkthrough by codestorywithMIK has 7,663 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 ith 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.length2 <= n <= 103bottomLeft[i].length == topRight[i].length == 21 <= bottomLeft[i][0], bottomLeft[i][1] <= 1071 <= topRight[i][0], topRight[i][1] <= 107bottomLeft[i][0] < topRight[i][0]bottomLeft[i][1] < topRight[i][1]Problem Overview: You are given multiple axis-aligned rectangles defined by bottom-left and top-right coordinates. For every pair of rectangles, compute their intersection region and determine the largest square that can fit entirely inside that overlap. Return the maximum possible square area among all rectangle pairs.
Approach 1: Brute Force Pair-Wise Intersection Checking (O(n2) time, O(1) space)
Check every pair of rectangles. For each pair, compute the intersection boundaries using left = max(x1a, x1b), right = min(x2a, x2b), bottom = max(y1a, y1b), and top = min(y2a, y2b). If right > left and top > bottom, the rectangles overlap. The largest square inside the overlap has side length min(right - left, top - bottom), and the area is that value squared. Track the maximum area across all pairs. This direct geometric check relies only on coordinate comparisons, making it easy to implement using concepts from geometry and arrays.
Approach 2: Sweep Line Algorithm (O(n log n + k) time, O(n) space)
Sort rectangle edges by their x-coordinates and sweep a vertical line from left to right. Maintain an active set of rectangles whose x-range intersects the sweep line. For rectangles currently active, check overlaps in the y-dimension and compute potential intersection regions. Whenever two rectangles overlap in both x and y, compute the candidate square side using the same min(width, height) rule. Sorting events takes O(n log n), and maintaining active rectangles introduces additional overlap checks. This approach reduces unnecessary comparisons when rectangles are far apart in the plane and is a standard technique in computational geometry problems involving interval intersections.
Recommended for interviews: Start with the brute force pair-wise intersection approach. It clearly demonstrates understanding of rectangle intersection math and runs in O(n^2), which is acceptable for moderate input sizes. If the interviewer pushes for optimization, discuss the sweep line technique that processes rectangles in sorted order and limits comparisons using active intervals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair-Wise Intersection | O(n^2) | O(1) | Small to medium number of rectangles. Simplest implementation for interviews. |
| Sweep Line Algorithm | O(n log n + k) | O(n) | Large datasets where many rectangles do not overlap. Reduces unnecessary pair checks. |