Sponsored
Sponsored
This approach involves treating rectangle edges as events (start and end), which we can sort and process sequentially. By sweeping across the x-axis and using a data structure, like Segment Tree or Balance Tree, to merge y-intervals, we can efficiently calculate the union area of rectangles.
Time Complexity: O(N^2 log N), where N is the number of rectangles. Sorting events takes O(N log N), and updating y-interval intervals can be up to O(N) operations for each event.
Space Complexity: O(N) for storing events and active intervals structures.
1def rectangleArea(rectangles):
2 MOD = 10**9 +
The solution uses a line sweep algorithm where rectangles are decomposed into events indicating if a horizontal segment is starting or ending. These events are sorted by the x-coordinate and processed to update the active intervals on the y-axis. A helper function manages merging y-intervals actively covered, calculating the cumulative area exposed over the previous segment width.
This approach involves using the inclusion-exclusion principle to calculate the area by adding all single rectangle areas and subtracting all pairwise overlaps calculated recursively. The approach is computationally intensive for the direct calculation but less error-prone for conceptual integrity.
Time Complexity: O(N log N), where the log component comes from interval set operations inherent in TreeMap.
Space Complexity: O(N), mainly for storing events and active structures.
1import java.util.*;
2
3public class RectangleAreaII {
4 public int rectangleArea(int[][] rectangles) {
5 int MOD = 1000000007;
6 List<Event> events = new ArrayList<>();
7 for (int[] rec : rectangles) {
8 events.add(new Event(rec[0], rec[1], rec[3], 1));
9 events.add(new Event(rec[2], rec[1], rec[3], -1));
10 }
11 events.sort(Comparator.comparingInt(a -> a.x));
12
13 TreeMap<Integer, Integer> active = new TreeMap<>();
14 long sum = 0, last_x = 0, last_y_sum = 0;
15 for (Event event : events) {
16 long x = event.x, type = event.type, y1 = event.y1, y2 = event.y2;
17 sum = (sum + last_y_sum * (x - last_x)) % MOD;
18 last_y_sum = 0;
19 if (type == 1) {
20 active.put(y1, active.getOrDefault(y1, 0) + type);
21 active.put(y2, active.getOrDefault(y2, 0) - type);
22 } else {
23 active.put(y1, active.getOrDefault(y1, 0) + type);
24 active.put(y2, active.getOrDefault(y2, 0) - type);
25 }
26
27 int prev = -1;
28 int count = 0;
29 for (Map.Entry<Integer, Integer> entry : active.entrySet()) {
30 if (count > 0) {
31 last_y_sum += entry.getKey() - prev;
32 }
33 count += entry.getValue();
34 prev = entry.getKey();
35 }
36 last_x = x;
37 }
38
39 return (int) sum;
40 }
41
42 class Event {
43 int x, y1, y2, type;
44
45 Event(int x, int y1, int y2, int type) {
46 this.x = x;
47 this.y1 = y1;
48 this.y2 = y2;
49 this.type = type;
50 }
51 }
52}This Java implementation uses a TreeMap to keep track of active y-intervals, adding or removing intervals based on the type of event being processed. The expansion of the x-coordinate determines how much additional area to count between events. The TreeMap simplifies the merging and tracking of overlapping y-intervals.
This approach uses the scanline technique combined with a segment tree to handle the union of rectangles. The scanline approach will treat each x-coordinate boundary as an event, i.e., where a rectangle starts or ends. These events allow efficient checking with a segment tree, which tracks active y-intervals.
Time complexity: O(N log N), where N is the number of events. This arises from sorting the events and using a segment tree for dynamic interval management.
Space complexity: O(N), for storing sorted y-coordinates and constructing the segment tree.
1class SegmentTree:
2 def __init__(self, n):
3 self.n = n
4 self.tree = [0] * (2 * n)
5 self.lazy = [0] * (2 * n)
6
7 def update(self, start, end, value, node, node_start, node_end):
8 if self.lazy[node] != 0:
9 self.tree[node] += (node_end - node_start + 1) * self.lazy[node]
10 if node_start != node_end: # not a leaf node
11 self.lazy[node * 2 + 1] += self.lazy[node]
12 self.lazy[node * 2 + 2] += self.lazy[node]
13 self.lazy[node] = 0
14
15 if start > node_end or end < node_start:
16 return
17 if start <= node_start and node_end <= end:
18 self.tree[node] += (node_end - node_start + 1) * value
19 if node_start != node_end:
20 self.lazy[node * 2 + 1] += value
21 self.lazy[node * 2 + 2] += value
22 return
23
24 mid = (node_start + node_end) // 2
25 self.update(start, end, value, 2 * node + 1, node_start, mid)
26 self.update(start, end, value, 2 * node + 2, mid + 1, node_end)
27 self.tree[node] = self.tree[node * 2 + 1] + self.tree[node * 2 + 2]
28
29 def query(self):
30 return self.tree[0]
31
32
33def rectangleArea(rectangles):
34 MOD = 10**9 + 7
35 events = []
36 y_coords = set()
37
38 for x1, y1, x2, y2 in rectangles:
39 events.append((x1, 1, y1, y2)) # entering, left boundary
40 events.append((x2, -1, y1, y2)) # leaving, right boundary
41 y_coords.update([y1, y2])
42
43 events.sort()
44 sorted_y = sorted(y_coords)
45 y_index = {v: i for i, v in enumerate(sorted_y)}
46
47 tree = SegmentTree(len(sorted_y))
48 current_x = events[0][0]
49 area = 0
50
51 for x, typ, y1, y2 in events:
52 area += tree.query() * (x - current_x)
53 area %= MOD
54 current_x = x
55 tree.update(y_index[y1], y_index[y2] - 1, typ, 0, 0, len(sorted_y) - 1)
56
57 return areaWe define a Segment Tree to manage y-coordinates, offering efficient updates for overlapping segments and interval covering. We iterate over event points in sorted order, updating the segment tree for each x-coordinate while calculating the area contribution to the result. Using modulo operation keeps the result scaled within bounds.
In this approach, we handle the vertical lines or events by consolidating intervals along the x-direction using coordinate compression. The active intervals along the y-axis are populated dynamically as the events are processed. Unlike a Segment Tree, this approach uses a simpler interval tracking to combine overlapping y-segments.
Time complexity: O(N log N), given the sorting of events and y-coordinates.
Space complexity: O(N), for event storage and y-indices tracking.
1import java.util.ArrayList;
2import java.util.HashSet;
3import java.util.List;
4import java.util.TreeMap;
5
6class Solution {
7 public int rectangleArea(int[][] rectangles) {
8 final int MOD = 1_000_000_007;
9 List<int[]> events = new ArrayList<>();
10 HashSet<Integer> yCoords = new HashSet<>();
11
12 for (int[] rect : rectangles) {
13 events.add(new int[]{rect[0], rect[1], rect[3], 1});
14 events.add(new int[]{rect[2], rect[1], rect[3], -1});
15 yCoords.add(rect[1]);
16 yCoords.add(rect[3]);
17 }
18
19 events.sort((a, b) -> Integer.compare(a[0], b[0]));
20 List<Integer> sortedY = new ArrayList<>(yCoords);
21 sortedY.sort(Integer::compareTo);
22 TreeMap<Integer, Integer> yIndex = new TreeMap<>();
23
24 for (int i = 0; i < sortedY.size(); i++) {
25 yIndex.put(sortedY.get(i), i);
26 }
27
28 int[] count = new int[sortedY.size() - 1];
29
30 int currentX = events.get(0)[0];
31 long area = 0;
32
33 for (int[] event : events) {
34 int x = event[0], y1 = event[1], y2 = event[2], type = event[3];
35 long lengthSum = 0;
36 for (int i = 0; i < count.length; i++) {
37 if (count[i] > 0) {
38 lengthSum += sortedY.get(i + 1) - sortedY.get(i);
39 }
40 }
41
42 area = (area + lengthSum * (x - currentX)) % MOD;
43 currentX = x;
44
45 for (int i = yIndex.get(y1); i < yIndex.get(y2); i++) {
46 count[i] += type;
47 }
48 }
49
50 return (int) area;
51 }
52}This approach defines events across x-coordinates, adjusting interval coverage along the y-axis using count to handle rectangle entry and exits succinctly. By employing coordinate compression and a simple interval logic, it systematically accumulates the total covered area.