Problem Description

Given two rectangles in a 2D plane, each defined by their bottom-left and top-right coordinates, calculate the total area covered by the two rectangles. If the rectangles overlap, the area of their overlap should only be counted once.

Each rectangle is represented by four integers: ax1, ay1, ax2, ay2 for the first rectangle and bx1, by1, bx2, by2 for the second rectangle, where:

• (ax1, ay1) and (ax2, ay2) are the bottom-left and top-right coordinates of the first rectangle.
• (bx1, by1) and (bx2, by2) are the bottom-left and top-right coordinates of the second rectangle.

Your task is to return the total area covered by the two rectangles.

Thought Process

The problem asks us to compute the combined area covered by two rectangles, making sure not to double-count any overlapping region. At first glance, the brute-force approach would be to "draw" both rectangles on a grid and count the number of covered cells, but this is inefficient and unnecessary.

Instead, we can use geometry: The area of each rectangle is easy to compute. If the rectangles do not overlap, the answer is just the sum of their areas. If they do overlap, we need to subtract the area of the overlapping region (which is counted twice).

The main challenge is to find the dimensions of the overlapping region, if any, and compute its area.

Solution Approach

Let's break down the solution step-by-step:

1. Compute the area of each rectangle:
   • Area of rectangle 1 = (ax2 - ax1) * (ay2 - ay1)
   • Area of rectangle 2 = (bx2 - bx1) * (by2 - by1)
2. Find overlap boundaries:
   • The overlapping rectangle (if any) will have:
     • Left boundary = max(ax1, bx1)
     • Right boundary = min(ax2, bx2)
     • Bottom boundary = max(ay1, by1)
     • Top boundary = min(ay2, by2)
3. Compute overlap area:
   • If right > left and top > bottom, then overlap exists and its area is (right - left) * (top - bottom).
   • If not, the rectangles do not overlap and overlap area is 0.
4. Sum areas and subtract overlap:
   • Total area = area1 + area2 - overlap_area

This approach is efficient and only involves a few arithmetic operations.

Example Walkthrough

Example:
Rectangle 1: (0, 0, 2, 2)
Rectangle 2: (1, 1, 3, 3)

1. Area1 = (2-0)*(2-0) = 4
2. Area2 = (3-1)*(3-1) = 4
3. Overlap boundaries:
   • Left = max(0,1) = 1
   • Right = min(2,3) = 2
   • Bottom = max(0,1) = 1
   • Top = min(2,3) = 2
4. Overlap area: (2-1)*(2-1) = 1*1 = 1
5. Total area = 4 + 4 - 1 = 7

The rectangles overlap in a 1x1 region, so we subtract this from the total.

Time and Space Complexity

• Brute-force approach: O(N^2) if we "draw" the rectangles on a grid, where N is the width/height of the grid. This is impractical for large coordinates.
• Optimized approach (current): O(1) time and O(1) space, since we only perform a fixed number of arithmetic operations regardless of the input values.

The optimized approach is much more efficient and suitable for all input sizes.

Summary

To solve the Rectangles Area problem, we:

• Calculated the area of each rectangle separately
• Determined the area of the overlapping region, if any
• Subtracted the overlap from the total to avoid double-counting

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 overlap_width = std::max(0, std::min(ax2, bx2) - std::max(ax1, bx1));
        int overlap_height = std::max(0, std::min(ay2, by2) - std::max(ay1, by1));
        int 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 = 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) {
    let area1 = (ax2 - ax1) * (ay2 - ay1);
    let area2 = (bx2 - bx1) * (by2 - by1);
    let overlapWidth = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
    let overlapHeight = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
    let overlapArea = overlapWidth * overlapHeight;
    return area1 + area2 - overlapArea;
};