Problem Breakdown
We are given a list of rectangles defined by their bottom-left and top-right coordinates (x1, y1) and (x2, y2). The goal is to calculate the total area covered by all these rectangles combined. Crucially, if two or more rectangles overlap, we must count that overlapping region only once (union area), not summing their individual areas which would double-count overlaps.
- Inputs: A list of lists
rects, where each inner list is[x1, y1, x2, y2]. - Outputs: An integer representing the total union area.
- Implicit Constraints & Edge Cases:
- Coordinates can be negative (standard Cartesian plane).
- Rectangles may not overlap at all or fully contain each other.
- Empty input list should return 0.
- Large coordinates: While Python handles large integers automatically, we must ensure the logic doesn’t rely on fixed-size arrays that would overflow in languages like C++/Java (though irrelevant for Python complexity).
- Degenerate rectangles where
x1 == x2ory1 == y2have zero area and should be ignored.
Intuition
A naive approach is to sum the individual areas of all rectangles ((x2-x1)*(y2-y1)), but this fails immediately because it counts overlaps multiple times. To fix this, we need a way to account for spatial relationships between shapes without checking every pair (which gets O(N^3) or worse).
Brute Force: Iterating through all pairs of rectangles to subtract intersection areas is complex and leads to exponential complexity in the worst case due to overlapping chains. Complexity: O(2^N) if we try inclusion-exclusion, or O(N^2) for pairwise intersections but still hard to manage overlaps correctly without a grid (which fails on sparse coordinates).
Key Insight: We can use a Line Sweep Algorithm. Imagine sweeping a vertical line from left to right across the plane. As this line moves:
- It encounters “events” where rectangles start (
x1) or end (x2). - Between two consecutive X-coordinates (where no rectangle starts/ends), the set of active Y-intervals remains constant.
- We can calculate how much height is covered by these active intervals in that strip and multiply it by the width of the strip to get area for that segment.
This reduces the problem from a complex geometric intersection task into sorting X-coordinates and managing 1D interval overlaps (Y-axis).
Approach
- Event Extraction: Collect all unique vertical edges (
x1andx2) from every rectangle. Sort these coordinates to define “strips” or intervals along the X-axis. - Sweep Line Iteration: Iterate through each adjacent pair of sorted X-coordinates
(prev_x, curr_x). The width iscurr_x - prev_x. - Active Intervals Check: For every strip between
prev_xandcurr_x, identify which rectangles are “active” (i.e., their x-range covers this entire interval). Collect the Y-intervals[y1, y2]for these active rectangles. - Height Calculation: Calculate the union length of all collected Y-intervals in that strip. This involves sorting intervals by
y1, then merging overlapping ones to find total covered height without double-counting overlaps within this specific X-strip. - Accumulate Area: Add
(width * merged_height)to a running total area.
Note: While implementing a Segment Tree would achieve O(N log N), it adds significant verbosity in Python for an interview setting. The Sweep Line with Interval Merging is often the expected “clean” solution unless strict constraints (N > 10k) are given, where we might discuss coordinate compression or segment trees as optimization paths.
Complexity Analysis
- Time: O(N^2). We iterate through sorted X-coordinates (O(N log N)) but for each strip, we scan all rectangles to find active ones and sort/merge Y-intervals which takes O(K log K) where K is the number of active rects. In worst case, this sums up to roughly quadratic behavior relative to input size in Python due to overhead.
- Space: O(N). We store sorted X-coordinates and temporary lists for active intervals per strip.
Solution
def rectangleArea(rects):
if not rects:
return 0
# Collect all unique x coordinates that define vertical boundaries
xs = set()
for r in rects:
xs.add(r[0])
xs.add(r[2])
sorted_xs = sorted(list(xs))
total_area = 0
# Iterate through each strip defined by adjacent X-coordinates
for i in range(len(sorted_xs) - 1):
x_curr, next_x = sorted_xs[i], sorted_xs[i+1]
if x_curr == next_x:
continue
width = next_x - x_curr
# Identify active rectangles that span this entire X-strip
# A rectangle is active if its left edge <= current strip start
# and right edge >= end of strip (strictly > prev_x)
y_intervals = []
for r in rects:
# Check if rect covers the interval [x_curr, next_x]
# Since we sorted unique Xs from all edges, any active rect must span this gap fully.
# We check x1 <= current strip start and x2 > current strip end (or >=)
# Actually simpler: r[0] < x_curr is not enough because rects might have started earlier.
# Correct logic for sweep line on unique Xs:
# If a rect starts at or before x_curr, it covers this interval if its right edge > next_x?
# Wait, standard approach: Filter rects where r[0] <= x_curr and r[2] >= next_x.
if r[0] < x_curr and r[2] > next_x:
y_intervals.append((r[1], r[3]))
# Calculate union length of Y intervals for this strip
if not y_intervals:
continue
# Sort by start coordinate to merge overlaps efficiently
y_intervals.sort(key=lambda x: x[0])
merged_height = 0
current_start, current_end = -float('inf'), float('-inf')
for interval in y_intervals:
if not (interval[0] > current_end):
# Overlaps or touches with previous active segment
current_end = max(current_end, interval[1])
else:
# No overlap, add the finished height and start new one
merged_height += current_end - current_start
current_start, current_end = interval
if not (current_start == float('-inf')):
merged_height += current_end - current_start
total_area += width * merged_height
return total_area
Edge Cases Handled
- Empty Input: Returns 0 immediately.
- No Overlaps: Logic naturally sums areas as intervals won’t merge, height equals sum of heights.
- Full Containment: Merging logic (
max(current_end)) handles a smaller rectangle inside a larger one correctly (height extends to the outer boundary). - Zero Width/Height Rectangles: Filtered out implicitly by coordinate sorting and interval math; if
x1 == x2, they won’t generate valid strips or intervals contributing area.