Rectangle Area Ii - Leetcode Solution

Problem Statement:

Given the coordinates of two rectangles in a 2D plane, compute the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and top-right corner (bx2, by2).

Assume that the area is never bigger than the maximum possible integer value.

Solution:

We can solve this problem by using the formula of the union of two rectangular regions. The formula for finding the area of the union of two rectangles is:

Area(Union) = Area(A) + Area(B) - Area(Overlap)

We will first calculate the area of the two rectangular regions A and B, and then calculate the area of the overlap.

Area(A) = (ax2 - ax1) * (ay2 - ay1) Area(B) = (bx2 - bx1) * (by2 - by1)

Next, we will calculate the overlap area. The overlap area can be calculated by finding the intersection of the two rectangles. The intersection rectangle will be defined by the bottom left coordinates (x1, y1) and top right coordinates (x2, y2). The overlap area will be:

Area(Overlap) = (x2 - x1) * (y2 - y1)

To find the intersection rectangle, we need to calculate the x and y coordinates of the bottom-left and top-right points of the intersection rectangle. The x coordinate of the bottom-left point will be the maximum of the x1 coordinate of the two rectangles, and the y coordinate of the bottom-left point will be the maximum of the y1 coordinate of the two rectangles. Similarly, the x coordinate of the top-right point will be the minimum of the x2 coordinate of the two rectangles, and the y coordinate of the top-right point will be the minimum of the y2 coordinate of the two rectangles.

x1 = max(ax1, bx1) y1 = max(ay1, by1) x2 = min(ax2, bx2) y2 = min(ay2, by2)

Now, we can use the above equations to calculate the area of the union of the two rectangles. The final formula will be:

Area(Union) = Area(A) + Area(B) - Area(Overlap) Area(Union) = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - (x2 - x1) * (y2 - y1)

We will implement the above algorithm in code as follows:

class Solution: def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:

    # Calculate the area of the two rectangles
    areaA = (ax2 - ax1) * (ay2 - ay1)
    areaB = (bx2 - bx1) * (by2 - by1)
    
    # Calculate the coordinates of intersection rectangle
    x1 = max(ax1, bx1)
    y1 = max(ay1, by1)
    x2 = min(ax2, bx2)
    y2 = min(ay2, by2)
    
    # Calculate the area of the overlap rectangle
    overlap = 0
    if x1 < x2 and y1 < y2:
        overlap = (x2 - x1) * (y2 - y1)
    
    # Calculate the area of the union of two rectangles
    area = areaA + areaB - overlap
    
    return area

Complexity Analysis:

The time complexity of the above algorithm is O(1) because we are performing constant computation to calculate the area of the two rectangles and the area of the overlap. The space complexity of the algorithm is O(1) because we are not using any extra space.

1