algoadvance

You are given the coordinates of two rectilinear rectangles in a 2D plane. The first rectangle is defined by its bottom-left corner (A, B) and its top-right corner (C, D), while the second rectangle is defined by its bottom-left corner (E, F) and its top-right corner (G, H).

Write a function to compute the total area covered by both rectangles.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. What should be done if the rectangles overlap?
    • Subtract the area of the overlapping region from the sum of the areas of the two rectangles.
  2. Are the rectangle coordinates always integers?
    • Yes.
  3. Can the rectangle be degenerate (line or point)?
    • No. Assume valid rectangles with positive area.

Strategy

  1. Calculate the Area of Each Rectangle Separately:
    • Area1 = (C - A) * (D - B)
    • Area2 = (G - E) * (H - F)
  2. Calculate the Area of the Overlapping Rectangle, if any:
    • The overlapping region, if it exists, will be a rectangle.
    • Determine the coordinates of this overlapping rectangle:
      • Left boundary: max(A, E)
      • Right boundary: min(C, G)
      • Bottom boundary: max(B, F)
      • Top boundary: min(D, H)
  3. Validate if These Boundaries Form a Valid Rectangle:
    • If the right boundary is to the left of the left boundary (or equal), or the top boundary is below the bottom boundary (or equal), there is no overlap.
  4. Calculate the Total Area:
    • Total area = Area1 + Area2 - Overlap Area (if there is an overlap).

Code

def compute_area(A, B, C, D, E, F, G, H):
    # Calculate area of the first rectangle
    area1 = (C - A) * (D - B)
    
    # Calculate area of the second rectangle
    area2 = (G - E) * (H - F)
    
    # Calculate the overlap boundaries
    overlap_left = max(A, E)
    overlap_right = min(C, G)
    overlap_bottom = max(B, F)
    overlap_top = min(D, H)
    
    # Initialize overlap area
    overlap_area = 0
    
    # Check if the overlap forms a valid rectangle
    if overlap_left < overlap_right and overlap_bottom < overlap_top:
        overlap_area = (overlap_right - overlap_left) * (overlap_top - overlap_bottom)
    
    # Calculate the total area
    total_area = area1 + area2 - overlap_area
    
    return total_area

# Example use cases
print(compute_area(-3, 0, 3, 4, 0, -1, 9, 2))  # Output: 45
print(compute_area(-2, -2, 2, 2, -2, -2, 2, 2))  # Output: 16

Time Complexity

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

Try our interview co-pilot at AlgoAdvance.com