850. Rectangle Area II

HardSegment TreeArrayOrdered SetLine Sweep

Problem Description

The task is to compute the total area covered by a set of rectangles in a 2D plane. Each rectangle is defined by its bottom-left and top-right corners. A crucial aspect of the problem is that if rectangles overlap, the overlapping area should only be counted once. This means that simply summing the areas of all rectangles will not suffice, as it could result in double-counting areas where rectangles intersect.

Intuition

To handle the complexity of overlapping rectangles, we break down the problem: First, we consider all edges of the rectangles (both left and right edges). These edges define "events" where we either start counting an area (left edge) or stop counting an area (right edge). To deal with vertical overlaps efficiently, we employ a sweep line algorithm with a segment tree.

The main idea is to sort the rectangle edges by their x-coordinates. As we sweep through the plane horizontally (left to right), we keep track of the y-coordinates of rectangle sides that are currently active, using a data structure that allows us to add or remove intervals (in this case, the y-intervals) efficiently. This is where the segment tree comes in handy. It allows us to add intervals (when we encounter a left edge) and remove intervals (when we encounter a right edge) while also keeping track of the total length of the covered interval on the y-axis at each step.

The segment tree is initialized with all unique y-coordinates of the rectangles to manage the intervals. We represent each segment tree node with the information of its y-interval, the count of how many rectangles are currently covering this interval (which can be incremented or decremented), and the length of the interval that is covered at least once.

When we move from one event to the next (from one x-coordinate to the next), we multiply the distance we have traveled on the x-axis with the total length of all the intervals that are currently covered on the y-axis. This gives us the area covered between these two x-coordinates, taking into account the vertical overlaps. We accumulate this area as we sweep through the events.

Finally, due to the possibility of very large numbers, the area is computed modulo 10⁹ + 7, a computational technique used to keep the numbers within manageable limits while performing arithmetic operations.

Learn more about Segment Tree and Line Sweep patterns.

Solution Approach

The implementation follows a comprehensive approach leveraging several computer science concepts, particularly the sweep line algorithm and segment tree data structure. Here's how we translate our intuition into a concrete solution:

Event Collection and Sorting:
- Create a list, segs, to represent the start and end events of the rectangles' y-intervals with their corresponding x-coordinates and an operation flag (1 for start, -1 for end).
- Populate another set, alls, with all unique y-coordinates in preparation for building the segment tree.
Segment Tree Setup:
- Initialize the segment tree, SegmentTree, using the sorted list derived from the set of y-coordinates.
- The tree structure is set up such that each node represents an interval with its bounds and maintains the total covered length and count of overlaps within that interval.
Sweep Line Algorithm:
- Sort segs based on x-coordinates to ensure that we process events in the correct order.
- Iterate through the events in segs. At each step, perform the following:
  - Update the area by adding the product of the distance between the current x-coordinate and the previous one (x - segs[i - 1][0]) with the current covered length from the segment tree (found in tree.length).
  - Modify the segment tree to reflect the current event using tree.modify method. This method adjusts the coverage count of relevant y-intervals based on whether it's a start or an end event (k is 1 when a rectangle begins and -1 when it ends).
- After each modification of the segment tree, rightly update the covered length of intervals.
Calculate the Final Area:
- Since the area might be vast, we take the modulo of the sum with 10^9 + 7 as per the problem's requirement before returning it as the result.

From the code, we observe:

The modify method on the segment tree adjusts the cnt for each node (interval), and subsequently updates the length that represents how much of each node's interval is covered.
The pushup method is responsible for updating the length of a node based on whether the node itself is covered or its child nodes are covered.

The solution makes efficient use of a segment tree to manage the y-intervals while sweeping through the x-coordinates, ensuring no overlapping area on the y-axis is counted more than once. By accumulating the areas of y-intervals as we progress along the x-axis, we obtain the total area covered by the rectangles without double-counting overlaps.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let us consider a set of three rectangles in a 2D plane with their corresponding bottom-left (bl) and top-right (tr) coordinates specified as follows:

Rectangle 1: bl(1,1), tr(3,3)
Rectangle 2: bl(2,2), tr(5,5)
Rectangle 3: bl(4,0), tr(6,2)

Each rectangle can be represented by two events: the start of the rectangle (left edge) and the end of the rectangle (right edge). We would thus have the following edges:

Rectangle 1 Start: (1, (1, 3), 1) where 1 is the x-coordinate, (1, 3) the y-interval, and 1 the operation flag.
Rectangle 1 End: (3, (1, 3), -1)
Rectangle 2 Start: (2, (2, 5), 1)
Rectangle 2 End: (5, (2, 5), -1)
Rectangle 3 Start: (4, (0, 2), 1)
Rectangle 3 End: (6, (0, 2), -1)

For events, we have two arrays:

Segs (for events): [(1, (1, 3), 1), (2, (2, 5), 1), (3, (1, 3), -1), (4, (0, 2), 1), (5, (2, 5), -1), (6, (0, 2), -1)]
Alls (for y-coordinates): [0, 1, 2, 3, 5]

We then sort segs based on x-coordinates and alls to prepare for building the segment tree.

Next, we construct the segment tree with alls and initialize all cnt to 0, as initially, no intervals are covered.

Now, let's process each event in segs:

Process the first event (Rectangle 1 Start at x=1). After adding the y-interval (1,3) to the segment tree, the active intervals are [1,3]. The total area is still zero since we don't have a previous x-coordinate to compare with just yet.
Move to the next event (Rectangle 2 Start at x=2). Update the current covered length and y-intervals to include [2,5], along with the previous [1,3]. The area added is the covered length from the segment tree multiplied by the x-distance traveled (2-1=1). So, the area at this point accounts for a vertical strip from x=1 to x=2.
Proceed to the third event (Rectangle 1 End at x=3). Remove the y-interval (1,3). The area added is the covered length (now excluding [1,3] but still including [2,5]) multiplied by the x-distance (3-2=1).
Do the same for the next events, always updating the area with the product of the x-distance traveled and the covered length from the segment tree.

Finally, the total area is accumulated by adding the segments' areas while accounting for overlaps in y-intervals, and the result is then taken modulo (10^9 + 7).

This example shows the essence of the sweep line algorithm with the segment tree data structure to calculate the total area covered by overlapping rectangles without double-counting any overlapping sections.

Solution Implementation

1from typing import List
2
3class Node:
4    def __init__(self):
5        # Initialize the left and right pointers of the segment
6        self.left = self.right = 0
7        # Initialize the segment count and the total length of segments covered
8        self.count = self.total_length = 0
9
10class SegmentTree:
11    def __init__(self, nums: List[int]):
12        # Set the number of elements in the nums list
13        n = len(nums) - 1
14        # Store the nums list
15        self.nums = nums
16        # Initialize the segment tree with nodes
17        self.tree = [Node() for _ in range(n << 2)]
18        # Build the segment tree
19        self.build(1, 0, n - 1)
20
21    def build(self, index: int, left: int, right: int):
22        # Set the range for this node
23        self.tree[index].left, self.tree[index].right = left, right
24        # If it is not a leaf node
25        if left != right:
26            # Calculate mid point to divide the range
27            mid = (left + right) >> 1
28            # Recursively build the left and right subtrees
29            self.build(index << 1, left, mid)
30            self.build(index << 1 | 1, mid + 1, right)
31
32    def modify(self, index: int, left: int, right: int, value: int):
33        if self.tree[index].left >= left and self.tree[index].right <= right:
34            # If the range is covered, update count
35            self.tree[index].count += value
36        else:
37            # If range covers partially, propagate the modification to children
38            mid = (self.tree[index].left + self.tree[index].right) >> 1
39            if left <= mid:
40                self.modify(index << 1, left, right, value)
41            if right > mid:
42                self.modify(index << 1 | 1, left, right, value)
43        # After modification, update the length of covered segments
44        self.pushup(index)
45
46    def pushup(self, index: int):
47        if self.tree[index].count:
48            # If count is non-zero, use the actual length
49            self.tree[index].total_length = self.nums[self.tree[index].right + 1] - self.nums[self.tree[index].left]
50        elif self.tree[index].left == self.tree[index].right:
51            # If it is a leaf node with zero count
52            self.tree[index].total_length = 0
53        else:
54            # If not, the length is the sum of lengths of the children
55            self.tree[index].total_length = self.tree[index << 1].total_length + self.tree[index << 1 | 1].total_length
56
57    @property
58    def length(self) -> int:
59        # Return total length of the segments represented by the tree
60        return self.tree[1].total_length
61
62class Solution:
63    def rectangleArea(self, rectangles: List[List[int]]) -> int:
64        # Initialize segments for y-coordinates and set of all y-coordinates
65        segments = []
66        all_y = set()
67        # Collect segments and unique y-coordinates
68        for x1, y1, x2, y2 in rectangles:
69            # Collect opening and closing segments
70            segments.append((x1, y1, y2, 1))
71            segments.append((x2, y1, y2, -1))
72            # Collect unique y-coordinates
73            all_y.update([y1, y2])
74
75        # Sort segments by x-coordinate and all_y by value
76        segments.sort()
77        all_y = sorted(all_y)
78      
79        # Create a segment tree instance
80        tree = SegmentTree(all_y)
81        # Map the y-coordinates to index in Segment Tree
82        y_to_index = {y: index for index, y in enumerate(all_y)}
83      
84        # Initialize the answer to 0
85        answer = 0
86        for i, (x, y1, y2, value) in enumerate(segments):
87            if i:
88                # Accumulate area between two x-coordinates
89                answer += tree.length * (x - segments[i - 1][0])
90            # Modify the segment tree to update counts
91            tree.modify(1, y_to_index[y1], y_to_index[y2] - 1, value)
92      
93        # Return the final answer modulo 1e9+7
94        answer %= int(1e9 + 7)
95        return answer
96

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4import java.util.TreeSet;
5
6class Node {
7    // Variables representing the interval's left and right boundaries,
8    // active count (how many rectangles cover this interval), and the
9    // total length covered by rectangles in this interval.
10    int left, right, count, length;
11}
12
13class SegmentTree {
14    private Node[] tree;
15    private int[] coordinates;
16
17    // Constructor initializes the segment tree with given coordinates.
18    public SegmentTree(int[] coordinates) {
19        this.coordinates = coordinates;
20        int n = coordinates.length - 1;
21        tree = new Node[n << 2]; // Size of segment tree array.
22        for (int i = 0; i < tree.length; ++i) {
23            tree[i] = new Node();
24        }
25        build(1, 0, n - 1);
26    }
27
28    // Build the segment tree recursively.
29    private void build(int u, int left, int right) {
30        tree[u].left = left;
31        tree[u].right = right;
32        if (left != right) {
33            int mid = (left + right) >> 1;
34            build(u << 1, left, mid);
35            build(u << 1 | 1, mid + 1, right);
36        }
37    }
38
39    // Update the segment tree by incrementing/decrementing counts over the interval [l, r].
40    public void modify(int u, int l, int r, int k) {
41        if (tree[u].left >= l && tree[u].right <= r) {
42            tree[u].count += k;
43        } else {
44            int mid = (tree[u].left + tree[u].right) >> 1;
45            if (l <= mid) {
46                modify(u << 1, l, r, k);
47            }
48            if (r > mid) {
49                modify(u << 1 | 1, l, r, k);
50            }
51        }
52        pushUp(u);
53    }
54
55    // Push up the changes in the segment tree from children to parent.
56    private void pushUp(int u) {
57        if (tree[u].count > 0) {
58            tree[u].length = coordinates[tree[u].right + 1] - coordinates[tree[u].left];
59        } else if (tree[u].left == tree[u].right) {
60            tree[u].length = 0;
61        } else {
62            tree[u].length = tree[u << 1].length + tree[u << 1 | 1].length;
63        }
64    }
65
66    // Query the total covered length in the segment tree.
67    public int query() {
68        return tree[1].length;
69    }
70}
71
72class Solution {
73    private static final int MOD = (int) 1e9 + 7;
74
75    // Computes the area of the union of rectangles provided in the input.
76    public int rectangleArea(int[][] rectangles) {
77        int n = rectangles.length;
78        int[][] segments = new int[n << 1][4];
79        int i = 0;
80        TreeSet<Integer> yCoordinates = new TreeSet<>();
81      
82        // Discretize the y-coordinates and prepare the segments.
83        for (int[] rect : rectangles) {
84            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
85            segments[i++] = new int[] {x1, y1, y2, 1}; // 'Start' segment.
86            segments[i++] = new int[] {x2, y1, y2, -1}; // 'End' segment.
87            yCoordinates.add(y1);
88            yCoordinates.add(y2);
89        }
90      
91        // Sort segments by their x-coordinate.
92        Arrays.sort(segments, (a, b) -> a[0] - b[0]);
93      
94        // Map the discrete y-coordinate to its index.
95        Map<Integer, Integer> map = new HashMap<>(yCoordinates.size());
96        i = 0;
97        int[] nums = new int[yCoordinates.size()];
98        for (int y : yCoordinates) {
99            map.put(y, i);
100            nums[i++] = y;
101        }
102
103        SegmentTree tree = new SegmentTree(nums);
104        long area = 0; // Use long to avoid overflow before taking modulo.
105      
106        // Traverse segments and actualize the total covered length accordingly.
107        for (i = 0; i < segments.length; ++i) {
108            int[] segment = segments[i];
109            int x = segment[0], y1 = segment[1], y2 = segment[2], k = segment[3];
110            if (i > 0) {
111                area += (long) tree.query() * (x - segments[i - 1][0]);
112            }
113            tree.modify(1, map.get(y1), map.get(y2) - 1, k);
114        }
115        area %= MOD; // Take modulo to fit into the specified range.
116        return (int) area; // Cast back to int since result is now within int range.
117    }
118}
119

1#include <vector>
2#include <set>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8// Definition of the Node class representing each segment tree node
9class Node {
10public:
11    int left, right, count, length;
12};
13
14// Definition of the SegmentTree class for handling interval modification and querying
15class SegmentTree {
16private:
17    vector<Node*> treeNodes; // Stores pointers to nodes of the segment tree
18    vector<int> sortedUniqueYCoordinates; // All unique y-coordinates sorted in ascending order
19
20    // Push up the calculated length from child nodes to the current node
21    void pushUp(int index) {
22        if (treeNodes[index]->count)
23            treeNodes[index]->length = sortedUniqueYCoordinates[treeNodes[index]->right + 1] - sortedUniqueYCoordinates[treeNodes[index]->left];
24        else if (treeNodes[index]->left == treeNodes[index]->right)
25            treeNodes[index]->length = 0;
26        else
27            treeNodes[index]->length = treeNodes[index << 1]->length + treeNodes[index << 1 | 1]->length;
28    }
29
30    // Build the segment tree
31    void build(int index, int left, int right) {
32        treeNodes[index]->left = left;
33        treeNodes[index]->right = right;
34        if (left != right) {
35            int mid = (left + right) >> 1;
36            build(index << 1, left, mid);
37            build(index << 1 | 1, mid + 1, right);
38        }
39    }
40
41public:
42    // Constructor initializes the segment tree
43    SegmentTree(vector<int>& nums) {
44        sortedUniqueYCoordinates = nums;
45        int n = nums.size() - 1;
46        treeNodes.resize(n << 2);
47        for (int i = 0; i < treeNodes.size(); ++i) treeNodes[i] = new Node();
48        build(1, 0, n - 1);
49    }
50
51    // Modify the count of nodes within a range [left, right] by value 'k'
52    void modify(int index, int left, int right, int k) {
53        if (treeNodes[index]->left >= left && treeNodes[index]->right <= right)
54            treeNodes[index]->count += k;
55        else {
56            int mid = (treeNodes[index]->left + treeNodes[index]->right) >> 1;
57            if (left <= mid) modify(index << 1, left, right, k);
58            if (right > mid) modify(index << 1 | 1, left, right, k);
59        }
60        pushUp(index);
61    }
62
63    // Query the total covered length in the segment tree
64    int query() {
65        return treeNodes[1]->length;
66    }
67};
68
69class Solution {
70public:
71    // Mod value to be used for obtaining the result within integer bounds
72    const int mod = 1e9 + 7;
73
74    // Function to calculate the area of rectangles
75    int rectangleArea(vector<vector<int>>& rectangles) {
76        int n = rectangles.size();
77        vector<vector<int>> segments(n << 1);
78        set<int> yAxisValues;
79        int index = 0;
80
81        // Extract and store rectangle coordinates, also populating the set
82        for (auto& rectangle : rectangles) {
83            int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
84            segments[index++] = {x1, y1, y2, 1};
85            segments[index++] = {x2, y1, y2, -1};
86            yAxisValues.insert(y1);
87            yAxisValues.insert(y2);
88        }
89
90        // Sort the segments by x-coordinate
91        sort(segments.begin(), segments.end());
92
93        // Map each y-coordinate to an index for array representation in the segment tree
94        unordered_map<int, int> y_to_index;
95        index = 0;
96        for (int yValue : yAxisValues) y_to_index[yValue] = index++;
97
98        // Converts the set of y-coordinates into a sorted vector
99        vector<int> sortedYCoords(yAxisValues.begin(), yAxisValues.end());
100
101        // Initialize the segment tree
102        SegmentTree* tree = new SegmentTree(sortedYCoords);
103      
104        long long answer = 0;
105        // Go through all segments, modifying the count in the segment tree, updating the answer
106        for (int i = 0; i < segments.size(); ++i) {
107            auto& segment = segments[i];
108            int x = segment[0], y1 = segment[1], y2 = segment[2], k = segment[3];
109            if (i > 0) answer += (long long) tree->query() * (x - segments[i - 1][0]);
110            tree->modify(1, y_to_index[y1], y_to_index[y2] - 1, k);
111        }
112
113        // Return the final area modulo mod
114        answer %= mod;
115        return (int) answer;
116    }
117};
118

1type Node = {
2  left: number;
3  right: number;
4  count: number;
5  length: number;
6};
7
8// Initialize a treeNodes array to hold the Node objects (Segment Tree)
9let treeNodes: Node[] = [];
10
11// Sorted unique y-coordinates used to determine the intervals
12let sortedUniqueYCoordinates: number[] = [];
13
14// Function to "push up" the calculated length from the child nodes to the current node
15function pushUp(index: number): void {
16  if (treeNodes[index].count > 0) {
17    treeNodes[index].length = sortedUniqueYCoordinates[treeNodes[index].right + 1] - sortedUniqueYCoordinates[treeNodes[index].left];
18  } else if (treeNodes[index].left === treeNodes[index].right) {
19    treeNodes[index].length = 0;
20  } else {
21    treeNodes[index].length = treeNodes[2 * index].length + treeNodes[2 * index + 1].length;
22  }
23}
24
25// Function to build the segment tree recursively for a given index and ranges [left, right]
26function build(index: number, left: number, right: number): void {
27  treeNodes[index] = { left, right, count: 0, length: 0 }; // Initialize the node
28  if (left !== right) {
29    const mid: number = Math.floor((left + right) / 2);
30    build(2 * index, left, mid);
31    build(2 * index + 1, mid + 1, right);
32  }
33}
34
35// Function to modify the count of nodes within a given range [left, right]
36function modify(index: number, left: number, right: number, deltaCount: number): void {
37  if (treeNodes[index].left >= left && treeNodes[index].right <= right) {
38    treeNodes[index].count += deltaCount;
39  } else {
40    const mid: number = Math.floor((treeNodes[index].left + treeNodes[index].right) / 2);
41    if (left <= mid) modify(2 * index, left, right, deltaCount);
42    if (right > mid) modify(2 * index + 1, left, right, deltaCount);
43  }
44  pushUp(index);
45}
46
47// Queries the total length that's covered in the segment tree
48function query(): number {
49  return treeNodes[1].length;
50}
51
52// Defines a constant mod value for integer boundary results
53const MOD: number = 1e9 + 7;
54
55// Function that calculates the area of rectangles
56function rectangleArea(rectangles: number[][]): number {
57  const n: number = rectangles.length;
58  const segments: number[][] = new Array(n * 2);
59  const yAxisValues: Set<number> = new Set();
60  let index: number = 0;
61
62  // Extract and store rectangle coordinates into segments and populate the set with y-axis values
63  rectangles.forEach(rectangle => {
64    const [x1, y1, x2, y2] = rectangle;
65    segments[index++] = [x1, y1, y2, 1];
66    segments[index++] = [x2, y1, y2, -1];
67    yAxisValues.add(y1);
68    yAxisValues.add(y2);
69  });
70
71  // Sort the segments based on the x-coordinate (along x-axis)
72  segments.sort((a, b) => a[0] - b[0]);
73
74  // Map y-coordinates to indices for array representation in the segment tree
75  const yAxisToIndex: Map<number, number> = new Map();
76  index = 0;
77  yAxisValues.forEach(yValue => yAxisToIndex.set(yValue, index++));
78
79  // Convert the set of y-coordinates to a sorted array
80  sortedUniqueYCoordinates = Array.from(yAxisValues).sort((a, b) => a - b);
81
82  // Initialize the segment tree with the y-coordinates
83  build(1, 0, sortedUniqueYCoordinates.length - 1); 
84
85  let answer: number = 0;
86  segments.forEach((segment, i) => {
87    const [x, y1, y2, k] = segment;
88    if (i > 0) {
89      const width = x - segments[i - 1][0];
90      answer += query() * width;
91      answer %= MOD; // Make sure to calculate modulo at each step to prevent overflow
92    }
93    modify(1, yAxisToIndex.get(y1)!, yAxisToIndex.get(y2)! - 1, k);
94  });
95
96  return answer;
97}
98

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into several parts:

Initialization of the Segment Tree (__init__ and build):
- The Segment Tree build function is called recursively and divides the range [l, r] into two halves each time. This division happens until each leaf represents a single element, which requires O(log n) time for each interval, with n being the number of unique y values.
- Since there's a total of O(n) unique y values to build the tree with, the initialization time complexity is O(n log n).
Modification of the Segment Tree (modify):
- The modify function is called for each x-coordinate in the list of segments. There are 2n x-coordinates because each rectangle contributes two (start and end), which makes it O(m), where m is twice the number of rectangles.
- Within the modify function, in the worst case, we update nodes all the way from the root to the leaves, and potentially all leaves in unbalanced cases. The tree has a height of O(log n), therefore the complexity of each modification is O(log n).
- This operation is repeated O(m) times (once for each distinct x-coordinate), leading to a time complexity of O(m log n) for all modifications.
Computation of the Total Length (in the loop within rectangleArea):
- We iterate through the sorted segments, and for each one, we update the tree and calculate the covered length. There are 2n segments, so the loop runs O(m) times.
- For each iteration, we calculate the covered length, which involves querying the root of the Segment Tree, which is an O(1) operation.
- The complexity of this part is dominated by the number of segments, which is O(m).

Overall, the time complexity is composed of the sum of the complexities of each part. Therefore, the final time complexity is primarily governed by the modify operation and is O(m log n) + O(n log n) + O(m), where m is twice the number of rectangles and n is the number of unique y values. Since O(m) is a subset of O(m log n), the overall time complexity simplifies to O(m log n).

Space Complexity

For space complexity:

Space for the Segment Tree (tr):
- A Segment Tree for n elements generally requires 4n space because it is a full binary tree, which amounts to O(n) space.
Space for Miscellaneous Variables and Data Structures (segs, alls, m):
- The segs list stores the start and end points of the segments and requires 2m spaces (since there are m rectangles and each rectangle contributes two segments).
- The alls set stores sorted unique y values and requires O(n) space.
- The mapping m also requires O(n) space.

Taking into consideration the maximum space required at any point in the program, the space complexity is O(n) + O(2m) + O(n) + O(n), which is O(n + m) overall. Here m is twice the number of rectangles, and n is the number of unique y values.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: