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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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:

  1. Determine the x and y ranges of each rectangle.
  2. Compute the overlapping range on the x-axis and the y-axis.
  3. 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

  1. Determine Rectangle Edges:
    • For each rectangle, compute the coordinates of the bottom-right corner using the top-left corner and the dimensions.
  2. 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.
  3. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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.