DSA problem
Rectangle Area II
You are given a 2D array rectangles where rectangles[i] = [x1_i, y1_i, x2_i, y2_i] denotes an axis-aligned rectangle with bottom-left corner (x1, y1) and top-right corner (x2, y2). Return the total area covered by all rectangles in the plane, where any overlapping area is counted exactly once. The answer may be very large, so return it modulo 10^9 + 7.
A naive approach of "union of rectangles" by drawing on a bitmap is hopeless because coordinates can be as large as 10^9. The classical trick is to sweep a vertical line from left to right while maintaining, in a separate data structure, the set of y-intervals currently active. When the sweep advances from x_curr to x_next the contribution to the total area is (x_next - x_curr) * unionLength(active y-intervals), evaluated before any events at x_next are processed.
To make the inner step fast, coordinate-compress the y-values: the union of all rectangles' y-coordinates partitions the y-axis into O(n) atomic intervals. A segment tree built over these atomic intervals stores, per node, a count of currently-active rectangles fully covering that node's range plus the length of "actively covered y" within its range. When a node's count is positive the entire node range is covered; otherwise its covered-length is the sum of its children's covered-lengths.
Events are generated per rectangle: an OPEN event (x1, +1, y1, y2) and a CLOSE event (x2, -1, y1, y2). Sort events by x. Sweep: for each distinct x, accumulate area using the current root covered-length, then apply all events at x to the segment tree (update each node's count by +/-1 along its update path). The total runtime is O(n log n) and the answer is taken modulo 10^9 + 7.
Examples
rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]6rectangles = [[0,0,1000000000,1000000000]]49rectangles = [[0,0,2,2],[2,0,4,2]]8Constraints
- 1 <= rectangles.length <= 200
- rectangles[i].length == 4
- 0 <= x1_i, y1_i, x2_i, y2_i <= 10^9
- x1_i < x2_i and y1_i < y2_i
- Result is taken modulo 10^9 + 7.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.