Watch 10 video solutions for Rectangle Area II, a hard level problem involving Array, Segment Tree, Line Sweep. This walkthrough by CodeWithSunny has 6,906 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.
Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.
Return the total area. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] Output: 6 Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture. From (1,1) to (2,2), the green and red rectangles overlap. From (1,0) to (2,3), all three rectangles overlap.
Example 2:
Input: rectangles = [[0,0,1000000000,1000000000]] Output: 49 Explanation: The answer is 1018 modulo (109 + 7), which is 49.
Constraints:
1 <= rectangles.length <= 200rectanges[i].length == 40 <= xi1, yi1, xi2, yi2 <= 109xi1 <= xi2yi1 <= yi2Problem Overview: Given multiple axis-aligned rectangles, compute the total area covered by them. Overlapping regions must be counted only once. Coordinates can be large, so the result is typically returned modulo 1e9+7. The challenge is efficiently handling overlapping intervals across many rectangles.
Approach 1: Line Sweep Using Event Sorting (O(n log n) time, O(n) space)
This approach treats every rectangle edge as an event in a vertical line sweep. For each rectangle, create two events: entering at x1 and leaving at x2. As you sweep from left to right, maintain active y-intervals and compute their merged length. The area added between two x-coordinates equals the merged vertical coverage multiplied by the horizontal distance moved. Maintaining intervals typically requires sorting and merging, giving O(n log n) complexity.
Approach 2: Inclusion-Exclusion Principle (O(n^2) time, O(1) extra space)
The inclusion-exclusion idea computes rectangle areas individually and subtracts pairwise overlaps. For two rectangles, compute the intersection region and subtract it from the sum of their areas. Extending this logic to multiple rectangles requires careful overlap handling and quickly becomes quadratic or worse. This method demonstrates the overlap concept but does not scale well for large inputs.
Approach 3: Scanline with Segment Tree (O(n log n) time, O(n) space)
This is the most robust solution and commonly expected in interviews. After sorting x-events, compress all unique y coordinates and maintain coverage counts in a segment tree. Each node tracks how much vertical length is currently covered. When processing an event, update the interval [y1, y2) with +1 or -1. The tree instantly returns the total active vertical length, allowing you to compute area contribution between consecutive x positions efficiently.
Approach 4: Line Sweeping with Interval Addition (O(n log n) time, O(n) space)
This variant keeps active intervals in an ordered structure such as a balanced tree or ordered set. When rectangles start or end, intervals are inserted or removed. The active intervals are merged to calculate the current vertical coverage. Compared to the segment tree method, this implementation is simpler but requires careful merging logic and can have higher constant factors.
Recommended for interviews: The scanline with segment tree approach. A basic sweep-line explanation shows you understand how overlapping areas accumulate, but the segment tree version demonstrates strong algorithmic design and efficient interval aggregation. Most competitive programming and system-level interview solutions use this pattern.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inclusion-Exclusion Principle | O(n^2) | O(1) | Conceptual understanding of overlapping rectangles or very small input sizes |
| Line Sweep with Event Sorting | O(n log n) | O(n) | General rectangle union problems where intervals can be merged dynamically |
| Scanline with Segment Tree | O(n log n) | O(n) | Best scalable solution for large inputs and common in competitive programming |
| Line Sweeping with Interval Addition | O(n log n) | O(n) | When using ordered sets or balanced trees to maintain active intervals |