Facebook Pixel

850. Rectangle Area II

HardSegment TreeArrayOrdered SetLine Sweep
Leetcode Link

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Add a y-interval when we encounter a rectangle's left edge (increment count)
  2. Remove a y-interval when we pass a rectangle's right edge (decrement count)
  3. 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]
  • 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 segment
    • cnt: count of how many intervals cover this segment
    • length: 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): Adds k 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
  • pushup(u): Updates the length of a node:
    • If cnt > 0: the entire segment is covered, so length = nums[r+1] - nums[l]
    • If cnt = 0 and it's a leaf: no coverage, so length = 0
    • If cnt = 0 and it's not a leaf: length = sum of children's lengths

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 Evaluator

Example 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 have 2n segments
  • Sorting unique y-coordinates: O(m log m) where m ≤ 2n
  • Building the segment tree: O(m)
  • Processing each segment with modify operation: O(n log m) since each modify takes O(log m) and we have 2n segments
  • Overall: O(n log n + m log m + n log m) = O(n log n) since m ≤ 2n

Space Complexity: O(n + m)

  • Segment list segs: O(n) storing 2n segments
  • Set and sorted list of y-coordinates alls: O(m) where m ≤ 2n
  • Segment tree nodes: O(4m) = O(m) since we allocate 4m nodes for the tree
  • Mapping dictionary m: O(m) for storing y-coordinate to index mapping
  • Overall: O(n + m) = O(n) since m ≤ 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
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Segment Tree

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

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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!

Load More