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]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.
C++
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.
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. |
LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python • NeetCode • 287,868 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