#850

Hard

LeetCode Problem Workspace

Rectangle Area II

The problem involves calculating the total area covered by multiple rectangles, ensuring overlap is counted only once.

array segment tree line sweep ordered set

Problem Statement

You are given an array of axis-aligned rectangles, where each rectangle is represented by four integers [xi1, yi1, xi2, yi2] corresponding to the bottom-left and top-right corners. The task is to calculate the total area covered by all these rectangles, while ensuring that overlapping areas are counted only once. The final result must be returned modulo 10^9 + 7.

The challenge lies in the efficient computation of the overlapping areas of these rectangles, given that their coordinates can range from 0 to 10^9. Direct area calculation may result in excessive time complexity. The optimal solution involves using data structures such as a Segment Tree and employing the Line Sweep technique to handle large inputs and overlapping efficiently.

Examples

Example 1

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]

Output: 6

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

The answer is 1018 modulo (109 + 7), which is 49.

Constraints

1 <= rectangles.length <= 200
rectanges[i].length == 4
0 <= xi1, yi1, xi2, yi2 <= 109
xi1 <= xi2
yi1 <= yi2
All rectangles have non zero area.

Solution Approach

Array and Segment Tree

This problem requires calculating the union of areas covered by multiple rectangles, which can be efficiently achieved using a Segment Tree. First, we need to sweep the rectangles vertically, and then use a Segment Tree to store and update the intervals covered by the rectangles.

Line Sweep Technique

The Line Sweep technique is used to process the rectangles by their x-coordinates. For each x-coordinate, we update the covered intervals in the Segment Tree. By sweeping through the rectangles from left to right, we ensure that overlaps are handled correctly and efficiently.

Modulo Operation for Large Output

Since the resulting area can be extremely large, we apply modulo 10^9 + 7 at each step to ensure that the solution remains manageable and fits within the problem constraints.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(N)

The time complexity of this solution is O(N^2), where N is the number of rectangles. This comes from the need to process each vertical line sweep, and for each such sweep, updating the Segment Tree, which takes O(N) time. The space complexity is O(N) due to the storage required for the Segment Tree and intermediate calculations.

What Interviewers Usually Probe

Candidate demonstrates understanding of the Line Sweep technique.
Candidate effectively utilizes Segment Tree to manage overlapping intervals.
Candidate correctly handles the modulo operation for large results.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the use of the Segment Tree and treating each rectangle independently.
Failing to handle large coordinate values properly, leading to inefficient solutions.
Neglecting the modulo operation when calculating the final area.

Follow-up variants

Allowing rectangles with negative coordinates.
Optimizing for rectangles with many overlapping areas.
Handling different types of non-rectangular shapes, such as polygons.

FAQ

What is the optimal approach for solving Rectangle Area II?

The optimal approach is to combine the Array and Segment Tree data structures with the Line Sweep technique to efficiently calculate the area while managing overlaps.

Why is a Segment Tree needed for this problem?

A Segment Tree helps efficiently manage and update the covered intervals for each vertical line sweep, ensuring accurate area calculation even with overlapping rectangles.

How does the Line Sweep technique work for Rectangle Area II?

The Line Sweep technique processes the rectangles by their x-coordinates, updating the Segment Tree for each rectangle's vertical projection. This allows for accurate tracking of overlapping regions.

Why do we use modulo 10^9 + 7 in this problem?

The modulo operation is used to ensure that the resulting area does not exceed the maximum allowed value, which is 10^9 + 7, as the answer may be too large to store in standard data types.

What are the time and space complexities of the solution?

The time complexity is O(N^2), where N is the number of rectangles, due to the line sweep and Segment Tree updates. The space complexity is O(N) for storing the Segment Tree and intermediate results.

terminal

Solution

Solution 1

#### Python3

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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

class Node:
    def __init__(self):
        self.l = self.r = 0
        self.cnt = self.length = 0


class SegmentTree:
    def __init__(self, nums):
        n = len(nums) - 1
        self.nums = nums
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 0, n - 1)

    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l != r:
            mid = (l + r) >> 1
            self.build(u << 1, l, mid)
            self.build(u << 1 | 1, mid + 1, r)

    def modify(self, u, l, r, k):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            self.tr[u].cnt += k
        else:
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            if l <= mid:
                self.modify(u << 1, l, r, k)
            if r > mid:
                self.modify(u << 1 | 1, l, r, k)
        self.pushup(u)

    def pushup(self, u):
        if self.tr[u].cnt:
            self.tr[u].length = self.nums[self.tr[u].r + 1] - self.nums[self.tr[u].l]
        elif self.tr[u].l == self.tr[u].r:
            self.tr[u].length = 0
        else:
            self.tr[u].length = self.tr[u << 1].length + self.tr[u << 1 | 1].length

    @property
    def length(self):
        return self.tr[1].length


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        segs = []
        alls = set()
        for x1, y1, x2, y2 in rectangles:
            segs.append((x1, y1, y2, 1))
            segs.append((x2, y1, y2, -1))
            alls.update([y1, y2])

        segs.sort()
        alls = sorted(alls)
        tree = SegmentTree(alls)
        m = {v: i for i, v in enumerate(alls)}
        ans = 0
        for i, (x, y1, y2, k) in enumerate(segs):
            if i:
                ans += tree.length * (x - segs[i - 1][0])
            tree.modify(1, m[y1], m[y2] - 1, k)
        ans %= int(1e9 + 7)
        return ans

Continue Practicing

#218 the skyline problem #731 my calendar ii #729 my calendar i