Rectangle Area II
Hard · Intervals · Array · Line Sweep · Ordered Set · Segment Tree
Problem
You are given a list of axis-aligned rectangles, where rectangles[i] = [x1, y1, x2, y2] gives the bottom-left corner (x1, y1) and the top-right corner (x2, y2).
Return the total area covered by the union of all the rectangles: a region covered by several rectangles counts only once. The result can be huge, so return it modulo 10^9 + 7.
Examples
Input: rectangles = [[0,0,3,3],[2,2,5,4]] Output: 14
The areas are 9 and 6, and they overlap in a 1 x 1 square: 9 + 6 - 1 = 14.
Input: rectangles = [[0,0,2,2],[0,0,1,1]] Output: 4
The second rectangle lies inside the first, so the union is the first: area 4.
Input: rectangles = [[0,0,100000,100000]] Output: 999999937
The area 10^10 is reduced modulo 10^9 + 7, giving 999999937.
Constraints
- 1 <= len(rectangles) <= 200
- len(rectangles[i]) == 4
- 0 <= x1, y1, x2, y2 <= 10^9
- x1 <= x2 and y1 <= y2
Approaches
- Baseline: compressed grid of cells — time O(n³), space O(n)
Follow-up
With a segment tree over the compressed y-coordinates, each node storing how many rectangles cover it fully and the covered length below it, every open or close event updates the covered length in O(log n), for O(n log n) overall. In JavaScript, areas up to 10^18 exceed the 2^53 range of exact doubles, so use BigInt for the products.
Related problems
Start free on Cariara · Coding problems · System design studio
