Geometry problems often look intimidating because of the coordinate math involved. However, this problem is a classic exercise in finding the overlap between shapes, a fundamental skill used in everything from game engines to graphics software.
Problem Summary
You're given:
- Two arrays,
bottomLeftandtopRight, representing the coordinates of rectangles on a 2D plane.
Your goal:
- Find the largest possible area of a square that can fit inside the intersection of any two rectangles. If no rectangles overlap, return 0.
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.
Intuition
To solve this, we need to break the problem down into two steps. First, we must find the intersection of two rectangles. Second, we must determine the largest square that can fit inside that intersection.
1. Finding the Intersection
When two rectangles overlap, their intersection is also a rectangle. We find its boundaries by:
- Taking the maximum of the bottom-left coordinates.
- Taking the minimum of the top-right coordinates.
If the resulting "top-right" coordinate is actually greater than the "bottom-left" coordinate in both and directions, an intersection exists.
2. Fitting the Square
A square has equal sides. If our intersection rectangle has a width and a height , the largest square we can fit inside it is limited by the shorter side. Therefore, the side length of the square will be . The area is then simply .
By iterating through every possible pair of rectangles, we can track the maximum area found so far.
Code Blocks
C++
class Solution {
public:
long long largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
long long maxArea = 0;
int n = bottomLeft.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Find the boundaries of the intersection
long long minX = max(bottomLeft[i][0], bottomLeft[j][0]);
long long maxX = min(topRight[i][0], topRight[j][0]);
long long minY = max(bottomLeft[i][1], bottomLeft[j][1]);
long long maxY = min(topRight[i][1], topRight[j][1]);
// Check if an intersection exists
if (minX < maxX && minY < maxY) {
long long side = min(maxX - minX, maxY - minY);
maxArea = max(maxArea, side * side);
}
}
}
return maxArea;
}
};
Python
class Solution:
def largestSquareArea(self, bottomLeft: list[list[int]], topRight: list[list[int]]) -> int:
max_area = 0
n = len(bottomLeft)
for i in range(n):
for j in range(i + 1, n):
# Calculate intersection boundaries
min_x = max(bottomLeft[i][0], bottomLeft[j][0])
max_x = min(topRight[i][0], topRight[j][0])
min_y = max(bottomLeft[i][1], bottomLeft[j][1])
max_y = min(topRight[i][1], topRight[j][1])
# If the rectangles overlap
if min_x < max_x and min_y < max_y:
side = min(max_x - min_x, max_y - min_y)
max_area = max(max_area, side * side)
return max_area
JavaScript
/**
* @param {number[][]} bottomLeft
* @param {number[][]} topRight
* @return {number}
*/
var largestSquareArea = function(bottomLeft, topRight) {
let maxArea = 0;
const n = bottomLeft.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// Determine the overlap region
let minX = Math.max(bottomLeft[i][0], bottomLeft[j][0]);
let maxX = Math.min(topRight[i][0], topRight[j][0]);
let minY = Math.max(bottomLeft[i][1], bottomLeft[j][1]);
let maxY = Math.min(topRight[i][1], topRight[j][1]);
// Check for valid intersection
if (minX < maxX && minY < maxY) {
let side = Math.min(maxX - minX, maxY - minY);
// Use BigInt if the problem constraints exceed 2^53 - 1
// For this specific problem, the max area is (10^7)^2 = 10^14
maxArea = Math.max(maxArea, side * side);
}
}
}
return maxArea;
};
Key Takeaways
-
Intersection Logic: Understanding how to find the overlap of two ranges by using
max()for starts andmin()for ends is a reusable pattern in interval and 2D problems. - Brute Force Pairing: For constraints where is up to 1000, an approach is efficient enough to pass within the time limit.
-
Constraint Awareness: When multiplying large numbers (like ), always use 64-bit integers (
long longin C++) to prevent overflow.
Final Thoughts
This problem serves as a great introduction to Computational Geometry. While it might feel like a math puzzle, these calculations are the backbone of modern UI systems. For instance, a browser's rendering engine uses similar logic to determine which parts of a window need to be redrawn when two app windows overlap. Mastering these coordinate checks will make you much more comfortable handling bounding boxes in professional software development.
Top comments (0)