850. Rectangle Area II
Problem Description
You are given a collection of axis-aligned rectangles on a 2D plane. Each rectangle is defined by four values [x1, y1, x2, y2]
where:
(x1, y1)
represents the bottom-left corner of the rectangle(x2, y2)
represents the top-right corner of the rectangle
Your task is to calculate the total area covered by all these rectangles combined. When rectangles overlap, the overlapping area should only be counted once (not multiple times).
For example, if two rectangles each have an area of 4 square units and they overlap by 1 square unit, the total covered area would be 7 square units (not 8).
Since the total area might be a very large number, you need to return the result modulo 10^9 + 7
.
The challenge involves handling overlapping rectangles correctly - you cannot simply sum up all individual rectangle areas because that would count overlapping regions multiple times. Instead, you need to find the union of all rectangles and calculate the area of that union.
Intuition
To find the total area covered by overlapping rectangles, we can think of this problem as a sweeping line problem. Imagine a vertical line sweeping from left to right across the plane.
At any given x-coordinate, this vertical line intersects with some rectangles, creating vertical segments. As we sweep from left to right, these vertical segments change - new segments appear when we encounter the left edge of a rectangle, and segments disappear when we pass the right edge of a rectangle.
The key insight is that between any two consecutive x-coordinates where rectangle edges occur, the vertical segments remain constant. So we can calculate the area as: (width between x-coordinates) × (total height of vertical segments)
.
For example, if between x = 2
and x = 5
(width = 3), our vertical line intersects segments covering heights from y = 1
to y = 3
and y = 4
to y = 6
(total height = 2 + 2 = 4), then the area for this section is 3 × 4 = 12
.
The challenge is efficiently tracking which y-intervals are "active" at each x-coordinate. This is where the segment tree comes in - it helps us:
- Add a y-interval when we encounter a rectangle's left edge (increment count)
- Remove a y-interval when we pass a rectangle's right edge (decrement count)
- Quickly calculate the total length of active y-intervals
We process events (rectangle edges) from left to right. For each rectangle, we create two events: one for the left edge (adding the y-interval [y1, y2]
) and one for the right edge (removing the y-interval [y1, y2]
). By processing these events in order and maintaining the active y-intervals, we can calculate the total area without double-counting overlaps.
Learn more about Segment Tree and Line Sweep patterns.
Solution Approach
The solution implements a sweep line algorithm with a segment tree to efficiently track and merge overlapping y-intervals. Here's how the implementation works:
1. Event Creation and Coordinate Compression:
- For each rectangle
[x1, y1, x2, y2]
, create two events:- Left edge event:
(x1, y1, y2, 1)
- adds the y-interval[y1, y2]
- Right edge event:
(x2, y1, y2, -1)
- removes the y-interval[y1, y2]
- Left edge event:
- Collect all unique y-coordinates and sort them for coordinate compression
- Map each y-coordinate to an index (0, 1, 2, ...) to work with the segment tree
2. Segment Tree Structure:
The SegmentTree
class maintains:
Node
objects with:l, r
: left and right boundaries of the segmentcnt
: count of how many intervals cover this segmentlength
: actual length covered in this segment
nums
: the sorted array of actual y-coordinates- The tree is built to manage intervals between consecutive y-coordinates
3. Core Operations:
modify(u, l, r, k)
: Addsk
to the count of interval[l, r]
- When
k = 1
: a new rectangle's y-interval is added - When
k = -1
: a rectangle's y-interval is removed
- When
pushup(u)
: Updates the length of a node:- If
cnt > 0
: the entire segment is covered, solength = nums[r+1] - nums[l]
- If
cnt = 0
and it's a leaf: no coverage, solength = 0
- If
cnt = 0
and it's not a leaf:length = sum of children's lengths
- If
4. Main Algorithm:
1. Sort all events by x-coordinate
2. Initialize [segment tree](/problems/segment_tree_intro) with compressed y-coordinates
3. For each event (x, y1, y2, k):
a. If not the first event:
- Calculate area: tree.length × (current_x - previous_x)
- Add to total area
b. Update segment tree:
- modify(1, m[y1], m[y2]-1, k)
- This adds/removes the y-interval [y1, y2]
4. Return total area % (10^9 + 7)
Example walkthrough:
For rectangles [[0,0,2,2], [1,0,3,1]]
:
- Events:
[(0,0,2,1), (1,0,1,1), (2,0,2,-1), (3,0,1,-1)]
- Y-coordinates:
[0, 1, 2]
→ indices{0:0, 1:1, 2:2}
- At
x=0
: Add interval[0,2]
, length = 2 - At
x=1
: Area += 2×(1-0) = 2, Add interval[0,1]
, length still 2 - At
x=2
: Area += 2×(2-1) = 2, Remove interval[0,2]
, length = 1 - At
x=3
: Area += 1×(3-2) = 1, Remove interval[0,1]
, length = 0 - Total area = 2 + 2 + 1 = 5
The segment tree efficiently handles the merging of overlapping y-intervals, ensuring each point is counted exactly once.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a simple example with two overlapping rectangles to illustrate the solution approach.
Input: rectangles = [[0,0,3,3], [2,1,4,4]]
These rectangles look like:
- Rectangle 1: bottom-left (0,0), top-right (3,3) - area = 9
- Rectangle 2: bottom-left (2,1), top-right (4,4) - area = 9
- They overlap in region [2,1] to [3,3] - overlap area = 2
Step 1: Create Events For each rectangle, we create a left edge event (add) and right edge event (remove):
- Rectangle 1:
(0, 0, 3, +1)
and(3, 0, 3, -1)
- Rectangle 2:
(2, 1, 4, +1)
and(4, 1, 4, -1)
Sorted events by x-coordinate: [(0,0,3,+1), (2,1,4,+1), (3,0,3,-1), (4,1,4,-1)]
Step 2: Coordinate Compression
Unique y-coordinates: [0, 1, 3, 4]
Mapping: {0:0, 1:1, 3:2, 4:3}
Step 3: Process Events with Segment Tree
Initialize segment tree with y-coordinates [0, 1, 3, 4].
At x = 0:
- Add interval [0,3] to segment tree (indices 0→2)
- Active y-coverage: from y=0 to y=3, length = 3
- No area calculation (first event)
At x = 2:
- Calculate area:
3 × (2-0) = 6
square units - Add interval [1,4] to segment tree (indices 1→3)
- Active y-coverage now:
- [0,1]: covered once (length = 1)
- [1,3]: covered twice (length = 2)
- [3,4]: covered once (length = 1)
- Total length = 4
At x = 3:
- Calculate area:
4 × (3-2) = 4
square units - Remove interval [0,3] from segment tree
- Active y-coverage: only [1,4] remains, length = 3
At x = 4:
- Calculate area:
3 × (4-3) = 3
square units - Remove interval [1,4] from segment tree
- Active y-coverage: none, length = 0
Total Area: 6 + 4 + 3 = 13 square units
This matches our expectation: Rectangle 1 (area 9) + Rectangle 2 (area 9) - Overlap (area 5) = 13.
The segment tree efficiently tracked the y-intervals at each x-position, automatically handling the overlap by maintaining counts of how many rectangles cover each segment. When multiple rectangles cover the same y-range, the segment tree ensures we only count that range once in our length calculation.
Solution Implementation
1from typing import List
2
3
4class SegmentTreeNode:
5 """Node for segment tree to track interval coverage."""
6
7 def __init__(self):
8 self.left_bound = 0 # Left boundary of the interval
9 self.right_bound = 0 # Right boundary of the interval
10 self.coverage_count = 0 # Number of times this interval is covered
11 self.covered_length = 0 # Total length covered in this interval
12
13
14class SegmentTree:
15 """Segment tree for maintaining covered length of y-axis intervals."""
16
17 def __init__(self, y_coordinates):
18 """
19 Initialize segment tree with compressed y-coordinates.
20
21 Args:
22 y_coordinates: Sorted list of unique y-coordinates
23 """
24 n = len(y_coordinates) - 1
25 self.y_coords = y_coordinates
26 self.tree = [SegmentTreeNode() for _ in range(n << 2)] # 4 * n nodes
27 self.build(1, 0, n - 1)
28
29 def build(self, node_idx, left, right):
30 """
31 Build the segment tree structure.
32
33 Args:
34 node_idx: Current node index in the tree
35 left: Left boundary of the interval
36 right: Right boundary of the interval
37 """
38 self.tree[node_idx].left_bound = left
39 self.tree[node_idx].right_bound = right
40
41 if left != right:
42 mid = (left + right) >> 1
43 # Build left child
44 self.build(node_idx << 1, left, mid)
45 # Build right child
46 self.build(node_idx << 1 | 1, mid + 1, right)
47
48 def modify(self, node_idx, query_left, query_right, delta):
49 """
50 Update coverage count for the interval [query_left, query_right].
51
52 Args:
53 node_idx: Current node index in the tree
54 query_left: Left boundary of query interval
55 query_right: Right boundary of query interval
56 delta: Change in coverage count (+1 for adding, -1 for removing)
57 """
58 current_node = self.tree[node_idx]
59
60 # If current interval is completely within query interval
61 if current_node.left_bound >= query_left and current_node.right_bound <= query_right:
62 current_node.coverage_count += delta
63 else:
64 mid = (current_node.left_bound + current_node.right_bound) >> 1
65 # Update left child if needed
66 if query_left <= mid:
67 self.modify(node_idx << 1, query_left, query_right, delta)
68 # Update right child if needed
69 if query_right > mid:
70 self.modify(node_idx << 1 | 1, query_left, query_right, delta)
71
72 self.push_up(node_idx)
73
74 def push_up(self, node_idx):
75 """
76 Update the covered length for the current node based on its coverage count.
77
78 Args:
79 node_idx: Current node index in the tree
80 """
81 current_node = self.tree[node_idx]
82
83 if current_node.coverage_count > 0:
84 # If covered, the length is the actual y-coordinate difference
85 current_node.covered_length = (
86 self.y_coords[current_node.right_bound + 1] -
87 self.y_coords[current_node.left_bound]
88 )
89 elif current_node.left_bound == current_node.right_bound:
90 # Leaf node with no coverage
91 current_node.covered_length = 0
92 else:
93 # Internal node: sum of children's covered lengths
94 left_child = self.tree[node_idx << 1]
95 right_child = self.tree[node_idx << 1 | 1]
96 current_node.covered_length = (
97 left_child.covered_length + right_child.covered_length
98 )
99
100 @property
101 def length(self):
102 """Get the total covered length of the y-axis."""
103 return self.tree[1].covered_length
104
105
106class Solution:
107 def rectangleArea(self, rectangles: List[List[int]]) -> int:
108 """
109 Calculate the total area covered by all rectangles.
110
111 Uses sweep line algorithm with segment tree for efficient computation.
112
113 Args:
114 rectangles: List of rectangles, each as [x1, y1, x2, y2]
115
116 Returns:
117 Total area covered by all rectangles modulo 10^9 + 7
118 """
119 # Prepare events for sweep line algorithm
120 events = []
121 y_coordinates = set()
122
123 for x1, y1, x2, y2 in rectangles:
124 # Add left edge (start of rectangle)
125 events.append((x1, y1, y2, 1))
126 # Add right edge (end of rectangle)
127 events.append((x2, y1, y2, -1))
128 # Collect all unique y-coordinates
129 y_coordinates.update([y1, y2])
130
131 # Sort events by x-coordinate
132 events.sort()
133
134 # Compress y-coordinates
135 sorted_y_coords = sorted(y_coordinates)
136 segment_tree = SegmentTree(sorted_y_coords)
137
138 # Map y-coordinate to compressed index
139 y_to_index = {y: idx for idx, y in enumerate(sorted_y_coords)}
140
141 # Process events and calculate area
142 total_area = 0
143
144 for i, (x, y1, y2, delta) in enumerate(events):
145 if i > 0:
146 # Add area from previous x to current x
147 width = x - events[i - 1][0]
148 height = segment_tree.length
149 total_area += width * height
150
151 # Update segment tree for current event
152 # Note: y2 - 1 because we're dealing with intervals
153 segment_tree.modify(1, y_to_index[y1], y_to_index[y2] - 1, delta)
154
155 # Return result modulo 10^9 + 7
156 MOD = int(1e9 + 7)
157 return total_area % MOD
158
1/**
2 * Node class for segment tree
3 * Stores interval information and coverage statistics
4 */
5class Node {
6 int left; // Left boundary of interval
7 int right; // Right boundary of interval
8 int coverageCount; // Number of times this interval is covered
9 int totalLength; // Total length covered in this interval
10}
11
12/**
13 * Segment Tree implementation for interval coverage
14 * Used to efficiently track and query covered lengths on a number line
15 */
16class SegmentTree {
17 private Node[] tree; // Array representation of segment tree
18 private int[] coordinates; // Sorted unique y-coordinates
19
20 /**
21 * Constructor to initialize segment tree
22 * @param coordinates Sorted array of unique y-coordinates
23 */
24 public SegmentTree(int[] coordinates) {
25 this.coordinates = coordinates;
26 int n = coordinates.length - 1;
27 // Allocate 4n space for segment tree array representation
28 tree = new Node[n << 2];
29 for (int i = 0; i < tree.length; ++i) {
30 tree[i] = new Node();
31 }
32 build(1, 0, n - 1);
33 }
34
35 /**
36 * Build segment tree recursively
37 * @param nodeIndex Current node index in tree array
38 * @param left Left boundary of current interval
39 * @param right Right boundary of current interval
40 */
41 private void build(int nodeIndex, int left, int right) {
42 tree[nodeIndex].left = left;
43 tree[nodeIndex].right = right;
44
45 // If not a leaf node, recursively build children
46 if (left != right) {
47 int mid = (left + right) >> 1;
48 build(nodeIndex << 1, left, mid); // Build left child
49 build(nodeIndex << 1 | 1, mid + 1, right); // Build right child
50 }
51 }
52
53 /**
54 * Modify coverage count for an interval
55 * @param nodeIndex Current node index
56 * @param left Left boundary of interval to modify
57 * @param right Right boundary of interval to modify
58 * @param delta Change in coverage count (+1 for add, -1 for remove)
59 */
60 public void modify(int nodeIndex, int left, int right, int delta) {
61 // If current interval is completely within target interval
62 if (tree[nodeIndex].left >= left && tree[nodeIndex].right <= right) {
63 tree[nodeIndex].coverageCount += delta;
64 } else {
65 // Recursively modify children that overlap with target interval
66 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
67 if (left <= mid) {
68 modify(nodeIndex << 1, left, right, delta);
69 }
70 if (right > mid) {
71 modify(nodeIndex << 1 | 1, left, right, delta);
72 }
73 }
74 pushup(nodeIndex);
75 }
76
77 /**
78 * Update total length covered in current node based on coverage count
79 * @param nodeIndex Current node index
80 */
81 private void pushup(int nodeIndex) {
82 if (tree[nodeIndex].coverageCount > 0) {
83 // If covered, length is the actual coordinate difference
84 tree[nodeIndex].totalLength = coordinates[tree[nodeIndex].right + 1] - coordinates[tree[nodeIndex].left];
85 } else if (tree[nodeIndex].left == tree[nodeIndex].right) {
86 // Leaf node with no coverage
87 tree[nodeIndex].totalLength = 0;
88 } else {
89 // Non-leaf node with no direct coverage, sum children's lengths
90 tree[nodeIndex].totalLength = tree[nodeIndex << 1].totalLength + tree[nodeIndex << 1 | 1].totalLength;
91 }
92 }
93
94 /**
95 * Query the total covered length
96 * @return Total length covered across all intervals
97 */
98 public int query() {
99 return tree[1].totalLength;
100 }
101}
102
103/**
104 * Solution class for calculating total area covered by rectangles
105 * Uses sweep line algorithm with segment tree
106 */
107class Solution {
108 private static final int MOD = (int) 1e9 + 7;
109
110 /**
111 * Calculate total area covered by union of rectangles
112 * @param rectangles Array of rectangles, each represented as [x1, y1, x2, y2]
113 * @return Total covered area modulo 10^9 + 7
114 */
115 public int rectangleArea(int[][] rectangles) {
116 int n = rectangles.length;
117 // Create events for sweep line: each rectangle generates 2 events (left and right edges)
118 int[][] events = new int[n << 1][4];
119 int eventIndex = 0;
120 TreeSet<Integer> uniqueYCoordinates = new TreeSet<>();
121
122 // Process each rectangle to create sweep line events
123 for (var rectangle : rectangles) {
124 int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
125 // Left edge event: add coverage
126 events[eventIndex++] = new int[] {x1, y1, y2, 1};
127 // Right edge event: remove coverage
128 events[eventIndex++] = new int[] {x2, y1, y2, -1};
129 uniqueYCoordinates.add(y1);
130 uniqueYCoordinates.add(y2);
131 }
132
133 // Sort events by x-coordinate for sweep line processing
134 Arrays.sort(events, (a, b) -> a[0] - b[0]);
135
136 // Coordinate compression: map y-coordinates to indices
137 Map<Integer, Integer> yCoordinateToIndex = new HashMap<>(uniqueYCoordinates.size());
138 eventIndex = 0;
139 int[] yCoordinates = new int[uniqueYCoordinates.size()];
140 for (int yCoord : uniqueYCoordinates) {
141 yCoordinateToIndex.put(yCoord, eventIndex);
142 yCoordinates[eventIndex++] = yCoord;
143 }
144
145 // Initialize segment tree with compressed y-coordinates
146 SegmentTree segmentTree = new SegmentTree(yCoordinates);
147 long totalArea = 0;
148
149 // Process events using sweep line algorithm
150 for (eventIndex = 0; eventIndex < events.length; ++eventIndex) {
151 var event = events[eventIndex];
152 int x = event[0], y1 = event[1], y2 = event[2], delta = event[3];
153
154 // Add area from previous x-position to current x-position
155 if (eventIndex > 0) {
156 totalArea += (long) segmentTree.query() * (x - events[eventIndex - 1][0]);
157 }
158
159 // Update coverage for y-interval [y1, y2)
160 segmentTree.modify(1, yCoordinateToIndex.get(y1), yCoordinateToIndex.get(y2) - 1, delta);
161 }
162
163 // Return result modulo 10^9 + 7
164 totalArea %= MOD;
165 return (int) totalArea;
166 }
167}
168
1class Node {
2public:
3 int left, right; // Range boundaries [left, right]
4 int count; // Number of active intervals covering this range
5 int coveredLength; // Total length covered in this range
6};
7
8class SegmentTree {
9public:
10 vector<Node*> tree;
11 vector<int> coordinates; // Sorted y-coordinates for mapping
12
13 SegmentTree(vector<int>& coords) {
14 this->coordinates = coords;
15 int n = coords.size() - 1;
16 tree.resize(n << 2); // 4 * n size for segment tree
17 for (int i = 0; i < tree.size(); ++i) {
18 tree[i] = new Node();
19 }
20 build(1, 0, n - 1);
21 }
22
23 // Build segment tree structure
24 void build(int nodeIdx, int left, int right) {
25 tree[nodeIdx]->left = left;
26 tree[nodeIdx]->right = right;
27 if (left != right) {
28 int mid = (left + right) >> 1;
29 build(nodeIdx << 1, left, mid); // Left child
30 build(nodeIdx << 1 | 1, mid + 1, right); // Right child
31 }
32 }
33
34 // Update the count of intervals covering range [left, right] by delta
35 void modify(int nodeIdx, int queryLeft, int queryRight, int delta) {
36 // If current node's range is completely within query range
37 if (tree[nodeIdx]->left >= queryLeft && tree[nodeIdx]->right <= queryRight) {
38 tree[nodeIdx]->count += delta;
39 } else {
40 int mid = (tree[nodeIdx]->left + tree[nodeIdx]->right) >> 1;
41 if (queryLeft <= mid) {
42 modify(nodeIdx << 1, queryLeft, queryRight, delta);
43 }
44 if (queryRight > mid) {
45 modify(nodeIdx << 1 | 1, queryLeft, queryRight, delta);
46 }
47 }
48 pushUp(nodeIdx);
49 }
50
51 // Query the total covered length at the root
52 int query() {
53 return tree[1]->coveredLength;
54 }
55
56 // Update covered length based on children or count
57 void pushUp(int nodeIdx) {
58 if (tree[nodeIdx]->count > 0) {
59 // If this range is covered, length is the actual coordinate difference
60 tree[nodeIdx]->coveredLength = coordinates[tree[nodeIdx]->right + 1] - coordinates[tree[nodeIdx]->left];
61 } else if (tree[nodeIdx]->left == tree[nodeIdx]->right) {
62 // Leaf node with no coverage
63 tree[nodeIdx]->coveredLength = 0;
64 } else {
65 // Non-leaf node: sum of children's covered lengths
66 tree[nodeIdx]->coveredLength = tree[nodeIdx << 1]->coveredLength +
67 tree[nodeIdx << 1 | 1]->coveredLength;
68 }
69 }
70};
71
72class Solution {
73public:
74 const int MOD = 1e9 + 7;
75
76 int rectangleArea(vector<vector<int>>& rectangles) {
77 int n = rectangles.size();
78 vector<vector<int>> sweepEvents(n << 1); // 2n events (left and right edges)
79 set<int> yCoordSet;
80 int eventIdx = 0;
81
82 // Create sweep line events and collect y-coordinates
83 for (auto& rect : rectangles) {
84 int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
85 sweepEvents[eventIdx++] = {x1, y1, y2, 1}; // Left edge: add interval
86 sweepEvents[eventIdx++] = {x2, y1, y2, -1}; // Right edge: remove interval
87 yCoordSet.insert(y1);
88 yCoordSet.insert(y2);
89 }
90
91 // Sort events by x-coordinate
92 sort(sweepEvents.begin(), sweepEvents.end());
93
94 // Map y-coordinates to indices for segment tree
95 unordered_map<int, int> yToIndex;
96 int index = 0;
97 for (int y : yCoordSet) {
98 yToIndex[y] = index++;
99 }
100
101 // Create sorted array of y-coordinates
102 vector<int> yCoordinates(yCoordSet.begin(), yCoordSet.end());
103
104 // Initialize segment tree
105 SegmentTree* segTree = new SegmentTree(yCoordinates);
106
107 long long totalArea = 0;
108
109 // Process sweep line events
110 for (int i = 0; i < sweepEvents.size(); ++i) {
111 auto event = sweepEvents[i];
112 int x = event[0], y1 = event[1], y2 = event[2], delta = event[3];
113
114 // Add area from previous x to current x
115 if (i > 0) {
116 totalArea += (long long) segTree->query() * (x - sweepEvents[i - 1][0]);
117 }
118
119 // Update the segment tree with the new interval
120 segTree->modify(1, yToIndex[y1], yToIndex[y2] - 1, delta);
121 }
122
123 totalArea %= MOD;
124 return (int) totalArea;
125 }
126};
127
1// Node structure for segment tree
2interface Node {
3 left: number; // Range left boundary
4 right: number; // Range right boundary
5 count: number; // Number of active intervals covering this range
6 coveredLength: number; // Total length covered in this range
7}
8
9// Global variables for segment tree
10let tree: Node[] = [];
11let coordinates: number[] = []; // Sorted y-coordinates for mapping
12
13// Build segment tree structure recursively
14function build(nodeIdx: number, left: number, right: number): void {
15 tree[nodeIdx] = {
16 left: left,
17 right: right,
18 count: 0,
19 coveredLength: 0
20 };
21
22 if (left !== right) {
23 const mid = (left + right) >> 1;
24 build(nodeIdx << 1, left, mid); // Build left child
25 build(nodeIdx << 1 | 1, mid + 1, right); // Build right child
26 }
27}
28
29// Update covered length based on children or count
30function pushUp(nodeIdx: number): void {
31 if (tree[nodeIdx].count > 0) {
32 // If this range is covered by at least one interval,
33 // length is the actual coordinate difference
34 tree[nodeIdx].coveredLength = coordinates[tree[nodeIdx].right + 1] - coordinates[tree[nodeIdx].left];
35 } else if (tree[nodeIdx].left === tree[nodeIdx].right) {
36 // Leaf node with no coverage
37 tree[nodeIdx].coveredLength = 0;
38 } else {
39 // Non-leaf node: sum of children's covered lengths
40 tree[nodeIdx].coveredLength = tree[nodeIdx << 1].coveredLength +
41 tree[nodeIdx << 1 | 1].coveredLength;
42 }
43}
44
45// Update the count of intervals covering range [queryLeft, queryRight] by delta
46function modify(nodeIdx: number, queryLeft: number, queryRight: number, delta: number): void {
47 // If current node's range is completely within query range
48 if (tree[nodeIdx].left >= queryLeft && tree[nodeIdx].right <= queryRight) {
49 tree[nodeIdx].count += delta;
50 } else {
51 const mid = (tree[nodeIdx].left + tree[nodeIdx].right) >> 1;
52 if (queryLeft <= mid) {
53 modify(nodeIdx << 1, queryLeft, queryRight, delta);
54 }
55 if (queryRight > mid) {
56 modify(nodeIdx << 1 | 1, queryLeft, queryRight, delta);
57 }
58 }
59 pushUp(nodeIdx);
60}
61
62// Query the total covered length at the root
63function query(): number {
64 return tree[1].coveredLength;
65}
66
67// Initialize segment tree with given coordinates
68function initializeSegmentTree(coords: number[]): void {
69 coordinates = coords;
70 const n = coords.length - 1;
71 tree = new Array(n << 2); // Allocate 4 * n size for segment tree
72 build(1, 0, n - 1);
73}
74
75// Main function to calculate total area of union of rectangles
76function rectangleArea(rectangles: number[][]): number {
77 const MOD = 1e9 + 7;
78 const n = rectangles.length;
79 const sweepEvents: number[][] = []; // Events for sweep line algorithm
80 const yCoordSet = new Set<number>();
81
82 // Create sweep line events and collect unique y-coordinates
83 for (const rect of rectangles) {
84 const [x1, y1, x2, y2] = rect;
85 sweepEvents.push([x1, y1, y2, 1]); // Left edge: add interval
86 sweepEvents.push([x2, y1, y2, -1]); // Right edge: remove interval
87 yCoordSet.add(y1);
88 yCoordSet.add(y2);
89 }
90
91 // Sort events by x-coordinate
92 sweepEvents.sort((a, b) => a[0] - b[0]);
93
94 // Create sorted array of y-coordinates
95 const yCoordinates = Array.from(yCoordSet).sort((a, b) => a - b);
96
97 // Map y-coordinates to indices for segment tree
98 const yToIndex = new Map<number, number>();
99 for (let i = 0; i < yCoordinates.length; i++) {
100 yToIndex.set(yCoordinates[i], i);
101 }
102
103 // Initialize segment tree with y-coordinates
104 initializeSegmentTree(yCoordinates);
105
106 let totalArea = 0;
107
108 // Process sweep line events from left to right
109 for (let i = 0; i < sweepEvents.length; i++) {
110 const [x, y1, y2, delta] = sweepEvents[i];
111
112 // Add area from previous x-coordinate to current x-coordinate
113 if (i > 0) {
114 const width = x - sweepEvents[i - 1][0];
115 const height = query();
116 totalArea = (totalArea + height * width) % MOD;
117 }
118
119 // Update the segment tree with the new interval
120 // Note: yToIndex[y2] - 1 because we're dealing with interval indices
121 modify(1, yToIndex.get(y1)!, yToIndex.get(y2)! - 1, delta);
122 }
123
124 return totalArea;
125}
126
Time and Space Complexity
Time Complexity: O(n log n + n log m)
where n
is the number of rectangles and m
is the number of unique y-coordinates.
- Creating segments and extracting unique y-coordinates:
O(n)
- Sorting segments:
O(n log n)
since we have2n
segments - Sorting unique y-coordinates:
O(m log m)
wherem ≤ 2n
- Building the segment tree:
O(m)
- Processing each segment with modify operation:
O(n log m)
since each modify takesO(log m)
and we have2n
segments - Overall:
O(n log n + m log m + n log m) = O(n log n)
sincem ≤ 2n
Space Complexity: O(n + m)
- Segment list
segs
:O(n)
storing2n
segments - Set and sorted list of y-coordinates
alls
:O(m)
wherem ≤ 2n
- Segment tree nodes:
O(4m) = O(m)
since we allocate4m
nodes for the tree - Mapping dictionary
m
:O(m)
for storing y-coordinate to index mapping - Overall:
O(n + m) = O(n)
sincem ≤ 2n
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Interval Indexing in Segment Tree
Pitfall: One of the most common mistakes is incorrectly handling the interval indices when calling modify()
. The segment tree works with compressed indices representing intervals between consecutive y-coordinates, not the y-coordinates themselves.
Incorrect approach:
# Wrong: Using y2 directly as the right boundary segment_tree.modify(1, y_to_index[y1], y_to_index[y2], delta)
Why it's wrong: If we have y-coordinates [0, 1, 2]
, the segment tree manages intervals [0,1)
and [1,2)
. For a rectangle with y-range [0,2]
, we need to cover both intervals (indices 0 and 1), but y_to_index[y2]
gives us 2, which would try to access a non-existent interval.
Correct approach:
# Correct: Using y2 - 1 to get the last interval index segment_tree.modify(1, y_to_index[y1], y_to_index[y2] - 1, delta)
2. Integer Overflow for Large Areas
Pitfall: Not handling potential integer overflow when calculating areas, especially before applying the modulo operation.
Incorrect approach:
# Potential overflow if width and height are large total_area += width * height
Correct approach:
# Apply modulo during calculation to prevent overflow total_area = (total_area + width * height) % MOD
3. Forgetting to Handle Empty Event List
Pitfall: Not checking for edge cases like empty rectangle list or single rectangle.
Solution: Add validation:
if not rectangles: return 0
4. Misunderstanding Coordinate Compression
Pitfall: Confusing the actual y-coordinates with their compressed indices. The segment tree operates on indices (0, 1, 2, ...), but when calculating actual lengths in push_up()
, we must use the original y-coordinates.
Wrong:
# Using indices instead of actual coordinates current_node.covered_length = current_node.right_bound + 1 - current_node.left_bound
Correct:
# Using actual y-coordinates for length calculation current_node.covered_length = ( self.y_coords[current_node.right_bound + 1] - self.y_coords[current_node.left_bound] )
5. Incorrect Tree Size Allocation
Pitfall: Allocating insufficient space for the segment tree. The tree needs approximately 4n nodes for n intervals.
Wrong:
self.tree = [SegmentTreeNode() for _ in range(n)] # Too small
Correct:
self.tree = [SegmentTreeNode() for _ in range(n << 2)] # 4 * n nodes
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Line Sweep Introduction The primary motivation for this algorithm is for geometry related problems that we encounter in computer science Deeply rooted in geometric problem solving it has become an essential tool for tackling questions related to shapes lines or points on a Cartesian plane At its heart the line
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!