223. Rectangle Area
Model: qwen3.5:9b
Topics: Math
FAANG asked: 0
Acceptance rate: 38.3%
Problem Breakdown
We are given two axis-aligned rectangles defined by their bottom-left and top-right coordinates: Rect1 is to , and Rect2 is to . The goal is to compute the total area covered by both combined. This effectively means calculating the union of the two areas.
Inputs: 8 integers representing coordinates ( for bottom-left; for top-right). Output: A single integer representing the sum of non-overlapping regions plus overlapping regions (counted once).
Implicit Constraints & Edge Cases:
- Coordinates can be negative.
- Rectangles might not overlap at all.
- One rectangle could completely contain the other.
- They might touch only along an edge or corner (intersection area is 0 in these cases).
- The problem guarantees valid rectangles where width and height are positive ( and , etc.), so we don’t need to validate input dimensions, but we must handle the intersection logic carefully.
Intuition
A naive approach might be to try counting pixels or iterating through a grid, which is impossible given coordinate ranges up to . That would lead to an area of roughly , requiring too much memory and time ( where is the bounding box size).
The key insight for this problem relies on set theory:
We can easily calculate the area of each individual rectangle. The challenge lies in calculating the intersection. Since rectangles are axis-aligned, their overlap (if it exists) is also a rectangle defined by the maximum of left edges and minimum of right edges for width, and similarly for height. If these boundaries don’t form a valid positive dimension, there is no overlap.
Approach
- Calculate Individual Areas: Compute
area1 = (C - A) * (D - B)andarea2 = (G - E) * (H - F). Note that since inputs guarantee bottom-left to top-right order, we don’t need absolute values here. - Define Intersection Boundaries: The intersection rectangle’s left edge is the maximum of both rectangles’ left edges (
max(A, E)). Its right edge is the minimum of their right edges (min(C, G)). Similarly for bottom and top:max(B, F)andmin(D, H). - Calculate Intersection Area: The width of intersection is
right - leftand height istop - bottom. If these values are negative (meaning no overlap), the area should be zero. We can use a helper function or logic to ensure we don’t subtract negative areas:intersection_area = max(0, right - left) * max(0, top - bottom). - Final Calculation: Return
area1 + area2 - intersection_area.
Complexity Analysis
- Time Complexity: . We perform a constant number of arithmetic operations regardless of the coordinate values (since we aren’t iterating).
- Space Complexity: . We only store a few variables for coordinates and areas. No additional data structures are required.
Solution
def computeArea(A, B, C, D, E, F, G, H):
# Calculate area of the first rectangle: width * height
area1 = (C - A) * (D - B)
# Calculate area of the second rectangle
area2 = (G - E) * (H - F)
# Determine boundaries for potential intersection
left_overlap = max(A, E)
right_overlap = min(C, G)
bottom_overlap = max(B, F)
top_overlap = min(D, H)
# Calculate width and height of the overlapping region.
# If there is no overlap, these will be negative or zero.
intersection_width = max(0, right_overlap - left_overlap)
intersection_height = max(0, top_overlap - bottom_overlap)
# Intersection area cannot be negative; if width/height <= 0, area is 0
intersection_area = intersection_width * intersection_height
# Apply the inclusion-exclusion principle: Union Area = Sum of Areas - Overlap
return area1 + area2 - intersection_area
Edge Cases Handled
- No Intersection: If
right_overlap <= left_overlaportop_overlap <= bottom_overlap, the width/height calculation results in 0 (due tomax(0, ...)), correctly yielding an overlap of 0. The result is simply sum of individual areas. - One Inside Another: The intersection logic naturally captures this; the smaller rectangle’s boundaries become the intersection limits, and subtracting that area from the larger one plus the small one results in just the large one (conceptually). Wait:
Area1 + Area2 - Intersection. If Rect2 is inside Rect1, Intersection = Area2. Result =Area1 + Area2 - Area2=Area1. Correct. - Touching Edges: If rectangles share an edge but don’t overlap in area (e.g., side-by-side), the width or height of intersection becomes 0, resulting in correct total sum.
- Negative Coordinates: The logic relies on relative differences (
C - Avsmax(A, E)). Since Python handles negative integers correctly and subtraction works as expected for coordinates regardless of sign (e.g.,-3 < 2), this is handled natively without special casing.