SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given the coordinates of two rectangles in a 2D plane, the task is to calculate the total area covered by the two rectangles. The rectangles may overlap, and the overlapping area should only be counted once.

Intuition

The problem is a classic example of geometry on a 2D plane. The key observation is that when two rectangles overlap, the area of overlap must be subtracted from the sum of the individual areas to avoid double-counting.

Approach

1. Calculate Overlapping Coordinates:

   • Determine the coordinates of the overlapping rectangle, if any. The left boundary of the overlap is the maximum of the left boundaries of the two rectangles, and the right boundary is the minimum of the right boundaries. Similarly, the top and bottom boundaries are determined using the y-coordinates.

2. Check for Valid Overlap:

   • Ensure that the calculated overlapping rectangle is valid (i.e., it has positive width and height).

3. Calculate Areas:

   • Calculate the area of the first and second rectangles independently.
   • Calculate the area of the overlapping region if there is an overlap.
   • The total area is then the sum of the areas of the two rectangles minus the overlapping area.

Complexity

Time Complexity:

O(1) - The solution involves a constant number of operations, regardless of the input size.

Space Complexity

:O(1) - No extra space is used apart from a few variables to store intermediate results.

Code

C++

class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, 
                    int bx1, int by1, int bx2, int by2) {

        int overLapX1 = std::max(ax1, bx1);
        int overLapX2 = std::min(ax2, bx2);
        int downY1 = std::max(ay1, by1);
        int upY2 = std::min(ay2, by2);

        int overlapArea = 0;
        if (overLapX2 > overLapX1 && upY2 > downY1) {
            overlapArea = (overLapX2 - overLapX1) * (upY2 - downY1);
        }

        int area1 = (ax2 - ax1) * (ay2 - ay1);
        int area2 = (bx2 - bx1) * (by2 - by1);
        
        return area1 + area2 - overlapArea;
    }
};

Python

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

        overLapX1 = max(ax1, bx1)
        overLapX2 = min(ax2, bx2)
        downY1 = max(ay1, by1)
        upY2 = min(ay2, by2)

        overlapArea = 0
        if overLapX2 > overLapX1 and upY2 > downY1:
            overlapArea = (overLapX2 - overLapX1) * (upY2 - downY1)

        area1 = (ax2 - ax1) * (ay2 - ay1)
        area2 = (bx2 - bx1) * (by2 - by1)
        
        return area1 + area2 - overlapArea

Java

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, 
                           int bx1, int by1, int bx2, int by2) {

        int overLapX1 = Math.max(ax1, bx1);
        int overLapX2 = Math.min(ax2, bx2);
        int downY1 = Math.max(ay1, by1);
        int upY2 = Math.min(ay2, by2);

        int overlapArea = 0;
        if (overLapX2 > overLapX1 && upY2 > downY1) {
            overlapArea = (overLapX2 - overLapX1) * (upY2 - downY1);
        }

        int area1 = (ax2 - ax1) * (ay2 - ay1);
        int area2 = (bx2 - bx1) * (by2 - by1);
        
        return area1 + area2 - overlapArea;
    }
}

JavaScript

/**
 * @param {number} ax1
 * @param {number} ay1
 * @param {number} ax2
 * @param {number} ay2
 * @param {number} bx1
 * @param {number} by1
 * @param {number} bx2
 * @param {number} by2
 * @return {number}
 */
var computeArea = function (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {

    const overLapX1 = Math.max(ax1, bx1);
    const overLapX2 = Math.min(ax2, bx2);
    const downY1 = Math.max(ay1, by1);
    const upY2 = Math.min(ay2, by2);

    let overlapArea = 0;
    if (overLapX2 - overLapX1 > 0 && upY2 - downY1 > 0) {
        overlapArea = (overLapX2 - overLapX1) * (upY2 - downY1);
    }
    const area1 = (ax2 - ax1) * (ay2 - ay1);
    const area2 = (bx2 - bx1) * (by2 - by1);
    
    return (area1 + area2 - overlapArea);
};