Problem
Given two rectangles on a 2D graph, return the area of their intersection. If the rectangles don’t intersect, return 0.
Examples
Example 1
Input:
Rectangle 1:
{
"top_left": (1, 4),
"dimensions": (3, 3) # width, height
}
Rectangle 2:
{
"top_left": (0, 5),
"dimensions": (4, 3) # width, height
}
Output: 6
Explanation: The two rectangles intersect in a 2x3 area, so the intersection area is 2 * 3 = 6.
Solution
Method 1 - Coordinate Geometry
To find the area of the intersection of two rectangles:
- Determine the x and y ranges of each rectangle.
- Compute the overlapping range on the x-axis and the y-axis.
- Calculate the intersection area by finding the width and height of the overlapping range. If there is no overlap, the intersection area is 0.
Approach
- Determine Rectangle Edges:
- For each rectangle, compute the coordinates of the bottom-right corner using the top-left corner and the dimensions.
- Compute Overlapping Range:
- Find the overlapping range on the x-axis by determining the maximum of the left edges and the minimum of the right edges.
- Find the overlapping range on the y-axis by determining the maximum of the bottom edges and the minimum of the top edges.
- Calculate Intersection Area:
- If the overlapping width and height are positive, multiply them to get the intersection area.
- If either width or height is zero or negative, there is no intersection.
Code
Java
public class Solution {
public static int intersectionArea(int[] rect1TopLeft, int[] rect1Dimensions, int[] rect2TopLeft, int[] rect2Dimensions) {
int x1 = rect1TopLeft[0];
int y1 = rect1TopLeft[1];
int x2 = x1 + rect1Dimensions[0];
int y2 = y1 - rect1Dimensions[1];
int x3 = rect2TopLeft[0];
int y3 = rect2TopLeft[1];
int x4 = x3 + rect2Dimensions[0];
int y4 = y3 - rect2Dimensions[1];
int overlapWidth = Math.min(x2, x4) - Math.max(x1, x3);
int overlapHeight = Math.min(y1, y3) - Math.max(y2, y4);
if (overlapWidth > 0 && overlapHeight > 0) {
return overlapWidth * overlapHeight;
} else {
return 0;
}
}
public static void main(String[] args) {
int[] rect1TopLeft = {1, 4};
int[] rect1Dimensions = {3, 3};
int[] rect2TopLeft = {0, 5};
int[] rect2Dimensions = {4, 3};
int result = intersectionArea(rect1TopLeft, rect1Dimensions, rect2TopLeft, rect2Dimensions);
System.out.println(result); // Output: 6
}
}
Python
class Solution:
def intersection_area(self, rect1: Dict[str, Tuple[int, int]], rect2: Dict[str, Tuple[int, int]]) -> int:
x1, y1 = rect1["top_left"]
w1, h1 = rect1["dimensions"]
x2, y2 = rect2["top_left"]
w2, h2 = rect2["dimensions"]
# Calculate bottom-right corners
x1_br, y1_br = x1 + w1, y1 - h1
x2_br, y2_br = x2 + w2, y2 - h2
# Calculate the overlapping ranges
overlap_width = min(x1_br, x2_br) - max(x1, x2)
overlap_height = min(y1, y2) - max(y1_br, y2_br)
if overlap_width > 0 and overlap_height > 0:
return overlap_width * overlap_height
else:
return 0
# Example usage
sol = Solution()
rect1 = {
"top_left": (1, 4),
"dimensions": (3, 3)
}
rect2 = {
"top_left": (0, 5),
"dimensions": (4, 3)
}
print(sol.intersection_area(rect1, rect2)) # Output: 6
Complexity
- ⏰ Time complexity:
O(1)
because the solution involves basic arithmetic computations that take constant time. - 🧺 Space complexity:
O(1)
since no additional space is required.