LeetCode: 223 Rectangle Area

LeetCode 223: Rectangle Area

https://leetcode.com/problems/rectangle-area/description/

Problem Description:
In a 2D plane, given two rectangles defined by their bottom-left and top-right corners, calculate the total area covered by the two rectangles (excluding any overlapping area).

You are given the coordinates of two rectangles:

(A, B) represents the bottom-left corner of the first rectangle
(C, D) represents the top-right corner of the first rectangle
(E, F) represents the bottom-left corner of the second rectangle
(G, H) represents the top-right corner of the second rectangle

Output:
Return the total area covered by the two rectangles.

Code Implementation:

class Solution:
    def computeArea(self, A: int, B: int, C: int, D: int, E: int, F: int, G: int, H: int) -> int:
        # Area of the first rectangle
        area1 = (C - A) * (D - B)
        # Area of the second rectangle
        area2 = (G - E) * (H - F)

        # Calculate the width and height of the overlapping area
        overlap_width = max(0, min(C, G) - max(A, E))
        overlap_height = max(0, min(D, H) - max(B, F))

        # Overlapping area
        overlap_area = overlap_width * overlap_height

        # Total area = sum of both areas minus the overlapping area
        total_area = area1 + area2 - overlap_area

        return total_area

Problem Analysis:

1. Understanding the definition of a rectangle:
   Each rectangle is defined by two coordinates: the bottom-left and top-right corners. Using these coordinates, we can easily calculate the area of each rectangle.

2. Calculating the area of a single rectangle:
   The formula for the area is:
   [
   \text{Area} = (\text{top-right x} – \text{bottom-left x}) \times (\text{top-right y} – \text{bottom-left y})
   ]
   We calculate the areas for both rectangles separately.

3. Finding the overlapping region:

   • The left boundary of the overlapping region is the greater of the two rectangles’ left boundaries: max(A, E).
   • The right boundary is the smaller of the two rectangles’ right boundaries: min(C, G).
   • The bottom boundary is the greater of the two rectangles’ bottom boundaries: max(B, F).
   • The top boundary is the smaller of the two rectangles’ top boundaries: min(D, H).

   If the right boundary is less than the left boundary or the top boundary is less than the bottom boundary, it means the rectangles do not overlap, and the overlapping area is 0.

4. Calculating the overlapping area:
   The formula for the overlapping area is:
   [
   \text{Overlapping Area} = \text{Width of Overlap} \times \text{Height of Overlap}
   ]
   Where:

   • Overlapping width = max(0, min(C, G) - max(A, E))
   • Overlapping height = max(0, min(D, H) - max(B, F))

5. Calculating the total area:
   Total area = sum of the areas of both rectangles minus the overlapping area.

Complexity Analysis:

• Time Complexity: O(1) – Calculating the area and the overlapping area takes constant time.
• Space Complexity: O(1) – We only use constant space to store the areas and boundary values.

Example Explanation:

Example 1:

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

• First rectangle area = (3 - (-3)) * (4 - 0) = 6 * 4 = 24
• Second rectangle area = (9 - 0) * (2 - (-1)) = 9 * 3 = 27
• Overlap width = max(0, min(3, 9) - max(-3, 0)) = 3
• Overlap height = max(0, min(4, 2) - max(0, -1)) = 2
• Overlap area = 3 * 2 = 6
• Total area = 24 + 27 - 6 = 45

Example 2:

Input: A = -2, B = -2, C = 2, D = 2, E = -2, F = -2, G = 2, H = 2
Output: 16

• Both rectangles completely overlap, so the total area equals the area of one rectangle = 4 * 4 = 16.

Key Takeaways:

1. The area of a rectangle is computed using its coordinates.
2. Special care must be taken when handling overlapping areas.
3. If no overlap exists, the overlapping area is 0.