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.
In this approach, we compare each pair of rectangles to determine the maximum possible overlap. We do this to calculate the largest square that can fit within any overlap region of two rectangles. This pairwise comparison, although basic, is manageable for small inputs and will ensure correctness.
This Python function calculates the largest square area by iterating over all pairs of rectangles and finding their overlapping area. If two rectangles overlap in a region where both dimensions are positive, it calculates the potential square's side length as the minimum of these overlaps. The maximum side length found across all pairs is used to calculate the square area.
Time Complexity: O(n^2), as it checks every pair of rectangles.
Space Complexity: O(1), since no extra space is required beyond variables for calculations.
The Sweep Line technique is efficient for interval problems in computational geometry. It entails sorting events and sweeping through them linearly. For this problem, treat rectangle edges as events and evaluate if the regions between these events allow for a larger square. This reduces the number of checks considerably, making the approach more efficient than checking each pair's overlap individually.
This Java solution uses a sweeping line through the x-axis where events (edges of rectangles) are added and sorted. For each x event, it keeps track of active y-ranges and checks for overlaps. By maintaining this map, it checks if the count of the overlapped ranges allows for placement of a square (requiring at least 2 overlapping rectangles). The solution is optimized using sorting and efficient y-range management, drastically limiting pairwise checks required.
Java
JavaScript
Time Complexity: O(n log n), due to sorting events and range queries.
Space Complexity: O(n), for storing events and active areas.
| Approach | Complexity |
|---|---|
| Brute Force Pair-Wise Intersection Checking | Time Complexity: O(n^2), as it checks every pair of rectangles. |
| Using Sweep Line Algorithm | Time Complexity: O(n log n), due to sorting events and range queries. |
| 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. |
Find the Largest Area of Square Inside Two Rectangles | Simple | Intuitive | Leetcode 3047 | MIK • codestorywithMIK • 7,663 views views
Watch 9 more video solutions →Practice Find the Largest Area of Square Inside Two Rectangles with our built-in code editor and test cases.
Practice on FleetCode