Problem

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.

Examples

Example 1:

1
2
3
4
5

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 rectangales, 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:

1
2
3

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 1018 modulo (10^9 + 7), which is 49.

We have seen similar problem - Rectangle Area - Total area of two rectangles

Solution

Method 1 – Line Sweep with Active Intervals

Intuition

To find the total area covered by rectangles (with overlaps counted only once), we can use a line sweep algorithm. We process all vertical edges (events) of rectangles, keep track of active intervals on the y-axis, and sum up the area covered as we sweep from left to right.

Approach

  1. For each rectangle, create two events: one for the left edge (add interval) and one for the right edge (remove interval).
  2. Sort all events by x-coordinate.
  3. Use a segment tree or a list to maintain active y-intervals.
  4. As we sweep from left to right, for each x, calculate the total y-length covered by active intervals and multiply by the width (difference in x) to get the area for that segment.
  5. Add up all such areas and return the result modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    int rectangleArea(vector<vector<int>>& R) {
        vector<int> Y;
        for (auto& r : R) Y.push_back(r[1]), Y.push_back(r[3]);
        sort(Y.begin(), Y.end());
        Y.erase(unique(Y.begin(), Y.end()), Y.end());
        vector<tuple<int, int, int, int>> events;
        for (auto& r : R) {
            events.emplace_back(r[0], r[1], r[3], 1);
            events.emplace_back(r[2], r[1], r[3], -1);
        }
        sort(events.begin(), events.end());
        vector<int> count(Y.size());
        int prev_x = 0, cur_y_sum = 0, res = 0;
        for (int i = 0; i < events.size(); ++i) {
            int x, y1, y2, sig;
            tie(x, y1, y2, sig) = events[i];
            res = (res + (long long)cur_y_sum * (x - prev_x)) % 1000000007;
            prev_x = x;
            for (int j = 0; j < Y.size(); ++j) {
                if (Y[j] >= y1 && Y[j] < y2) count[j] += sig;
            }
            cur_y_sum = 0;
            for (int j = 0; j < Y.size()-1; ++j) {
                if (count[j] > 0) cur_y_sum += Y[j+1] - Y[j];
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import "sort"
func rectangleArea(R [][]int) int {
    mod := int(1e9+7)
    Y := []int{}
    for _, r := range R {
        Y = append(Y, r[1], r[3])
    }
    sort.Ints(Y)
    Y = unique(Y)
    type event struct{ x, y1, y2, sig int }
    events := []event{}
    for _, r := range R {
        events = append(events, event{r[0], r[1], r[3], 1})
        events = append(events, event{r[2], r[1], r[3], -1})
    }
    sort.Slice(events, func(i, j int) bool { return events[i].x < events[j].x })
    count := make([]int, len(Y))
    prevX, curY, res := 0, 0, 0
    for i := 0; i < len(events); i++ {
        x, y1, y2, sig := events[i].x, events[i].y1, events[i].y2, events[i].sig
        res = (res + curY*(x-prevX)) % mod
        prevX = x
        for j := 0; j < len(Y); j++ {
            if Y[j] >= y1 && Y[j] < y2 {
                count[j] += sig
            }
        }
        curY = 0
        for j := 0; j < len(Y)-1; j++ {
            if count[j] > 0 {
                curY += Y[j+1] - Y[j]
            }
        }
    }
    return res
}
func unique(a []int) []int {
    n := len(a)
    if n == 0 { return a }
    res := []int{a[0]}
    for i := 1; i < n; i++ {
        if a[i] != a[i-1] {
            res = append(res, a[i])
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public int rectangleArea(int[][] R) {
        Set<Integer> ySet = new HashSet<>();
        for (int[] r : R) {
            ySet.add(r[1]); ySet.add(r[3]);
        }
        List<Integer> Y = new ArrayList<>(ySet);
        Collections.sort(Y);
        List<int[]> events = new ArrayList<>();
        for (int[] r : R) {
            events.add(new int[]{r[0], r[1], r[3], 1});
            events.add(new int[]{r[2], r[1], r[3], -1});
        }
        events.sort((a, b) -> a[0] - b[0]);
        int[] count = new int[Y.size()];
        int prevX = 0, curY = 0, res = 0;
        for (int i = 0; i < events.size(); i++) {
            int[] e = events.get(i);
            int x = e[0], y1 = e[1], y2 = e[2], sig = e[3];
            res = (int)((res + (long)curY * (x - prevX)) % 1000000007);
            prevX = x;
            for (int j = 0; j < Y.size(); j++) {
                if (Y.get(j) >= y1 && Y.get(j) < y2) count[j] += sig;
            }
            curY = 0;
            for (int j = 0; j < Y.size()-1; j++) {
                if (count[j] > 0) curY += Y.get(j+1) - Y.get(j);
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun rectangleArea(R: Array<IntArray>): Int {
        val mod = 1_000_000_7
        val Y = mutableListOf<Int>()
        for (r in R) { Y.add(r[1]); Y.add(r[3]) }
        val yList = Y.distinct().sorted()
        val events = mutableListOf<IntArray>()
        for (r in R) {
            events.add(intArrayOf(r[0], r[1], r[3], 1))
            events.add(intArrayOf(r[2], r[1], r[3], -1))
        }
        events.sortBy { it[0] }
        val count = IntArray(yList.size)
        var prevX = 0
        var curY = 0
        var res = 0
        for (e in events) {
            val (x, y1, y2, sig) = e
            res = ((res + 1L * curY * (x - prevX)) % mod).toInt()
            prevX = x
            for (j in yList.indices) {
                if (yList[j] >= y1 && yList[j] < y2) count[j] += sig
            }
            curY = 0
            for (j in 0 until yList.size-1) {
                if (count[j] > 0) curY += yList[j+1] - yList[j]
            }
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def rectangleArea(self, R: list[list[int]]) -> int:
        MOD = 10**9+7
        Y = sorted(set([y for x1, y1, x2, y2 in R for y in (y1, y2)]))
        events = []
        for x1, y1, x2, y2 in R:
            events.append((x1, y1, y2, 1))
            events.append((x2, y1, y2, -1))
        events.sort()
        count = [0]*len(Y)
        prev_x = 0
        cur_y_sum = 0
        res = 0
        for x, y1, y2, sig in events:
            res = (res + cur_y_sum * (x - prev_x)) % MOD
            prev_x = x
            for j in range(len(Y)):
                if Y[j] >= y1 and Y[j] < y2:
                    count[j] += sig
            cur_y_sum = 0
            for j in range(len(Y)-1):
                if count[j] > 0:
                    cur_y_sum += Y[j+1] - Y[j]
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

impl Solution {
    pub fn rectangle_area(rectangles: Vec<Vec<i32>>) -> i32 {
        let mut y = vec![];
        for r in &rectangles {
            y.push(r[1]);
            y.push(r[3]);
        }
        y.sort();
        y.dedup();
        let mut events = vec![];
        for r in &rectangles {
            events.push((r[0], r[1], r[3], 1));
            events.push((r[2], r[1], r[3], -1));
        }
        events.sort();
        let mut count = vec![0; y.len()];
        let mut prev_x = 0;
        let mut cur_y_sum = 0;
        let mut res = 0i64;
        for (x, y1, y2, sig) in events {
            res = (res + cur_y_sum * (x - prev_x) as i32 as i64) % 1_000_000_007;
            prev_x = x;
            for j in 0..y.len() {
                if y[j] >= y1 && y[j] < y2 {
                    count[j] += sig;
                }
            }
            cur_y_sum = 0;
            for j in 0..y.len()-1 {
                if count[j] > 0 {
                    cur_y_sum += y[j+1] - y[j];
                }
            }
        }
        res as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    rectangleArea(R: number[][]): number {
        const MOD = 1e9+7;
        const Y: number[] = [];
        for (const r of R) Y.push(r[1], r[3]);
        Y.sort((a, b) => a - b);
        const yList = Array.from(new Set(Y));
        const events: [number, number, number, number][] = [];
        for (const r of R) {
            events.push([r[0], r[1], r[3], 1]);
            events.push([r[2], r[1], r[3], -1]);
        }
        events.sort((a, b) => a[0] - b[0]);
        const count = new Array(yList.length).fill(0);
        let prevX = 0, curY = 0, res = 0;
        for (const [x, y1, y2, sig] of events) {
            res = (res + curY * (x - prevX)) % MOD;
            prevX = x;
            for (let j = 0; j < yList.length; j++) {
                if (yList[j] >= y1 && yList[j] < y2) count[j] += sig;
            }
            curY = 0;
            for (let j = 0; j < yList.length-1; j++) {
                if (count[j] > 0) curY += yList[j+1] - yList[j];
            }
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(N^2 log N), where N is the number of rectangles. Each event may update O(N) intervals.
  • 🧺 Space complexity: O(N), for storing events and active intervals.