Code Implementation

class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int,
                          bx1: int, by1: int, bx2: int, by2: int) -> int:
        area1 = (ax2 - ax1) * (ay2 - ay1)
        area2 = (bx2 - bx1) * (by2 - by1)
        overlap_width = max(0, min(ax2, bx2) - max(ax1, bx1))
        overlap_height = max(0, min(ay2, by2) - max(ay1, by1))
        overlap_area = overlap_width * overlap_height
        return area1 + area2 - overlap_area
      

class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2,
                    int bx1, int by1, int bx2, int by2) {
        int area1 = (ax2 - ax1) * (ay2 - ay1);
        int area2 = (bx2 - bx1) * (by2 - by1);
        int overlapWidth = std::max(0, std::min(ax2, bx2) - std::max(ax1, bx1));
        int overlapHeight = std::max(0, std::min(ay2, by2) - std::max(ay1, by1));
        int overlapArea = overlapWidth * overlapHeight;
        return area1 + area2 - overlapArea;
    }
};
      

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2,
                           int bx1, int by1, int bx2, int by2) {
        int area1 = (ax2 - ax1) * (ay2 - ay1);
        int area2 = (bx2 - bx1) * (by2 - by1);
        int overlapWidth = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
        int overlapHeight = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
        int overlapArea = overlapWidth * overlapHeight;
        return area1 + area2 - overlapArea;
    }
}
      

var computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
    const area1 = (ax2 - ax1) * (ay2 - ay1);
    const area2 = (bx2 - bx1) * (by2 - by1);
    const overlapWidth = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
    const overlapHeight = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
    const overlapArea = overlapWidth * overlapHeight;
    return area1 + area2 - overlapArea;
};
      

Problem Description

You are given the coordinates of two rectangles in a 2D plane. Each rectangle is defined by its bottom-left and top-right coordinates: (ax1, ay1, ax2, ay2) for the first rectangle and (bx1, by1, bx2, by2) for the second rectangle. The rectangles may overlap, touch, or be completely separate.

Your task is to compute the total area covered by both rectangles. If the rectangles overlap, the overlapped area should only be counted once in the total area.

Constraints:

• All coordinates are integers.
• Coordinates are such that ax1 < ax2 and ay1 < ay2 (similarly for bx1, bx2, by1, by2).
• There is no guarantee that the rectangles overlap.

Thought Process

At first glance, the problem seems straightforward: just add the areas of the two rectangles. However, if the rectangles overlap, the overlapping region will be counted twice. To get the correct total area, we need to make sure the overlapped part is only counted once.

A brute-force approach might consider marking every point covered by the rectangles, but this is inefficient and unnecessary. Instead, we can use geometry to calculate the overlapped area directly by finding the intersection of the two rectangles.

The main challenge is to correctly compute the width and height of the overlapping region, if any, and subtract that from the sum of the individual rectangle areas.

Solution Approach

• Step 1: Calculate the area of each rectangle.
  • The area of a rectangle defined by its bottom-left (x1, y1) and top-right (x2, y2) corners is (x2 - x1) * (y2 - y1).
• Step 2: Find the overlap dimensions.
  • The overlap in the x-direction is from max(ax1, bx1) to min(ax2, bx2).
  • The overlap in the y-direction is from max(ay1, by1) to min(ay2, by2).
  • If these ranges are negative or zero, there is no overlap (so use max(0, ...)).
• Step 3: Compute the overlap area.
  • Multiply the overlap width and overlap height to get the overlap area.
• Step 4: Compute the final area.
  • Add the areas of both rectangles and subtract the overlap area.

This approach is efficient and uses only basic arithmetic operations.

Example Walkthrough

Let's use the following example:

• Rectangle A: (0, 0, 2, 2)
• Rectangle B: (1, 1, 3, 3)

1. Calculate each area:
   • Area A = (2 - 0) * (2 - 0) = 4
   • Area B = (3 - 1) * (3 - 1) = 4
2. Calculate overlap:
   • Overlap width = min(2, 3) - max(0, 1) = 2 - 1 = 1
   • Overlap height = min(2, 3) - max(0, 1) = 2 - 1 = 1
   • Overlap area = 1 * 1 = 1
3. Compute total area:
   • Total = 4 + 4 - 1 = 7
4. Result:
   • The area covered by both rectangles is 7.

Time and Space Complexity

• Brute-force approach:
  • If we were to check every unit point in the bounding box of both rectangles, the time complexity would be O((maxX - minX) * (maxY - minY)), which is inefficient for large coordinates.
• Optimized approach:
  • All calculations are done in constant time using arithmetic operations and comparisons.
  • Time Complexity: O(1)
  • Space Complexity: O(1)

Summary

The solution leverages basic geometry to efficiently compute the total area covered by two rectangles, handling overlap by subtracting the intersection area. This approach is both elegant and efficient, requiring only constant time and space, and avoids unnecessary computations. The key insight is to directly compute the overlap region using max/min operations, ensuring correct results for all possible rectangle positions.