algoadvance

Leetcode 223. Rectangle Area

Problem Statement

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

Each rectangle is defined by its bottom-left corner and top-right corner as (A, B) and (C, D) for the first rectangle, and (E, F) and (G, H) for the second rectangle.

Clarifying Questions

  1. Will the input always represent valid rectangles (i.e., ( A < C ) and ( B < D ) for the first rectangle and ( E < G ) and ( F < H ) for the second rectangle)?
  2. Do the coordinates lie within a specific range (e.g., all inputs are within the 32-bit signed integer range)?
  3. Is overlap always possible, or can the rectangles be completely separate or touching but not overlapping?

Code

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        // Calculate the area of both the rectangles separately
        int area1 = (C - A) * (D - B);
        int area2 = (G - E) * (H - F);
        
        // Calculate the overlapping area
        int overlapWidth = max(0, min(C, G) - max(A, E));
        int overlapHeight = max(0, min(D, H) - max(B, F));
        int overlapArea = overlapWidth * overlapHeight;
        
        // Total area covered by both rectangles
        int totalArea = area1 + area2 - overlapArea;
        
        return totalArea;
    }
};

Strategy

  1. Calculate Individual Areas: Compute the areas of the two rectangles independently.
  2. Determine Overlap Dimensions: Calculate the overlapping width and height.
    • The width of the overlapping area is the difference between the smallest of the top-right corners and the largest of the bottom-left corners along the x-axis.
    • The height follows a similar calculation along the y-axis.
  3. Compute Overlap Area: Multiply the overlap dimensions to get the overlap area. Ensure that if the rectangles do not overlap, the overlap area should be zero.
  4. Total Coverage Area: Calculate the total area by adding the areas of both rectangles and subtracting the overlap area.

Time Complexity

The time complexity of this solution is ( O(1) ) because it involves a fixed number of arithmetic operations and comparisons regardless of the actual input values.

Example

For the rectangles defined by (A, B, C, D) as (0, 0, 2, 2) and (E, F, G, H) as (1, 1, 3, 3):

  1. Calculate individual areas: ( 2 \times 2 = 4 ) for the first rectangle, and ( 2 \times 2 = 4 ) for the second.
  2. Determine overlap: The overlap has width ( \min(2, 3) - \max(0, 1) = 1 ) and height ( \min(2, 3) - \max(0, 1) = 1 ), thus an overlap area of ( 1 \times 1 = 1 ).
  3. Total area: ( 4 + 4 - 1 = 7 ).

This approach ensures accurate calculation of the total area covered by the two rectangles, accounting correctly for any overlaps.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI