Rectangle Area II

• Create two sorted lists of unique coordinates, one for all x-coordinates (x_coords) and one for all y-coordinates (y_coords) from the input rectangles.
• These sorted coordinates define a grid. An elementary rectangle (a cell in the grid) is formed by (x_coords[j], y_coords[i]) and (x_coords[j+1], y_coords[i+1]).
• Create a 2D boolean array grid with dimensions (number of unique y's) x (number of unique x's) to keep track of which elementary rectangles are covered.
• For each input rectangle, iterate through the elementary rectangles it covers and mark the corresponding entry in the grid as true.
• Initialize total_area = 0.
• Iterate through the grid. If grid[i][j] is true, calculate the area of the corresponding elementary rectangle: width = x_coords[j+1] - x_coords[j] and height = y_coords[i+1] - y_coords[i].
• Add the product (width * height) to total_area, taking the result modulo 10^9 + 7 at each step.
• Return the final total_area.

The core idea is to break down the problem from a continuous plane to a discrete grid. The boundaries of this grid are defined by the x and y coordinates of all the given rectangles.

First, we collect all unique x-coordinates (both x1 and x2) and all unique y-coordinates (y1 and y2) from the rectangles. We sort these unique coordinates to form two lists, x_coords and y_coords. These lists define the grid lines.

Next, we can create a 2D boolean array, say covered_grid, where covered_grid[i][j] corresponds to the elementary rectangle defined by corners (x_coords[j], y_coords[i]) and (x_coords[j+1], y_coords[i+1]). We iterate through each input rectangle and for each one, we find the range of indices in x_coords and y_coords it spans. We then mark all the cells in covered_grid within this range as true.

Finally, we iterate through the covered_grid. For each cell (i, j) that is marked true, we calculate its area and add it to a running total. The area of cell (i, j) is (x_coords[j+1] - x_coords[j]) * (y_coords[i+1] - y_coords[i]). Since the total area can be very large, all calculations are performed using long and the sum is taken modulo 10^9 + 7.

1import java.util.*;2 3class Solution {4    public int rectangleArea(int[][] rectangles) {5        int MOD = 1_000_000_007;6        7        Set<Integer> xSet = new TreeSet<>();8        Set<Integer> ySet = new TreeSet<>();9        10        for (int[] rect : rectangles) {11            xSet.add(rect[0]);12            xSet.add(rect[2]);13            ySet.add(rect[1]);14            ySet.add(rect[3]);15        }16        17        List<Integer> xCoords = new ArrayList<>(xSet);18        List<Integer> yCoords = new ArrayList<>(ySet);19        20        Map<Integer, Integer> xMap = new HashMap<>();21        for (int i = 0; i < xCoords.size(); i++) {22            xMap.put(xCoords.get(i), i);23        }24        25        Map<Integer, Integer> yMap = new HashMap<>();26        for (int i = 0; i < yCoords.size(); i++) {27            yMap.put(yCoords.get(i), i);28        }29        30        boolean[][] grid = new boolean[yCoords.size()][xCoords.size()];31        32        for (int[] rect : rectangles) {33            int x1 = xMap.get(rect[0]);34            int x2 = xMap.get(rect[2]);35            int y1 = yMap.get(rect[1]);36            int y2 = yMap.get(rect[3]);37            38            for (int i = y1; i < y2; i++) {39                for (int j = x1; j < x2; j++) {40                    grid[i][j] = true;41                }42            }43        }44        45        long totalArea = 0;46        for (int i = 0; i < yCoords.size() - 1; i++) {47            for (int j = 0; j < xCoords.size() - 1; j++) {48                if (grid[i][j]) {49                    long width = xCoords.get(j + 1) - xCoords.get(j);50                    long height = yCoords.get(i + 1) - yCoords.get(i);51                    totalArea = (totalArea + (width * height)) % MOD;52                }53            }54        }55        56        return (int) totalArea;57    }58}

• For each rectangle [x1, y1, x2, y2], create two events: an 'enter' event (x1, y1, y2, 1) and a 'leave' event (x2, y1, y2, -1).
• Store all these events in a list and sort them primarily by their x-coordinate.
• Initialize total_area = 0, last_x to the x-coordinate of the first event, and an empty list active_intervals to store the y-intervals [y1, y2] of rectangles currently intersecting the sweep line.
• Iterate through the sorted events:
  • Let the current event's x-coordinate be current_x.
  • Calculate the width of the vertical strip: width = current_x - last_x.
  • If width > 0, calculate the total length of the union of active_intervals. This is done by sorting active_intervals and merging them to find the total covered length on the y-axis.
  • Add (width * covered_length) to total_area (modulo 10^9 + 7).
  • Process all events at current_x: if it's an 'enter' event, add its y-interval to active_intervals; if it's a 'leave' event, remove it.
  • Update last_x = current_x.
• Return the final total_area.

The plane sweep algorithm works by calculating area incrementally. We consider a vertical sweep line that moves from left to right. The total area is the sum of areas of vertical strips between consecutive x-coordinates where something changes.

1. Events: A change occurs at the left and right edges of each rectangle. We model these as events. For each rectangle [x1, y1, x2, y2], we generate two events: (x1, y1, y2, +1) signifying the start of a rectangle, and (x2, y1, y2, -1) signifying the end. We collect all 2N events.

2. Sorting: We sort these events based on their x-coordinate. This gives us the sequence of positions for our sweep line.

3. Sweeping: We iterate through the sorted events. Let's say we are moving from last_x to current_x. The width of this strip is current_x - last_x. In this strip, the set of active rectangles is constant. The height of the covered region in this strip is the length of the union of the y-intervals of all active rectangles.

4. Calculating Height: To calculate this covered height, we maintain a list of active y-intervals. At each step, we can sort these intervals and merge them to find the total length. For example, if active intervals are [0, 2] and [1, 3], their union is [0, 3] with length 3.

5. Updating State: When the sweep line passes an event at current_x, we update our list of active intervals. For a start event, we add its y-interval. For an end event, we remove it. Then we update last_x to current_x and proceed to the next event.

This approach is more efficient than grid discretization, but the repeated sorting of active intervals is a bottleneck.

1import java.util.*;2 3class Solution {4    public int rectangleArea(int[][] rectangles) {5        int MOD = 1_000_000_007;6        List<int[]> events = new ArrayList<>();7        for (int[] rect : rectangles) {8            // event: [x, y1, y2, type], type 1 for start, -1 for end9            events.add(new int[]{rect[0], rect[1], rect[3], 1});10            events.add(new int[]{rect[2], rect[1], rect[3], -1});11        }12 13        Collections.sort(events, (a, b) -> a[0] - b[0]);14 15        long totalArea = 0;16        long lastX = events.get(0)[0];17        List<int[]> activeIntervals = new ArrayList<>();18 19        for (int i = 0; i < events.size(); ) {20            int currentX = events.get(i)[0];21            long width = currentX - lastX;22 23            if (width > 0) {24                long yLength = 0;25                if (!activeIntervals.isEmpty()) {26                    Collections.sort(activeIntervals, (a, b) -> a[0] - b[0]);27                    int start = activeIntervals.get(0)[0];28                    int end = activeIntervals.get(0)[1];29                    for (int j = 1; j < activeIntervals.size(); j++) {30                        int[] interval = activeIntervals.get(j);31                        if (interval[0] < end) {32                            end = Math.max(end, interval[1]);33                        } else {34                            yLength += (end - start);35                            start = interval[0];36                            end = interval[1];37                        }38                    }39                    yLength += (end - start);40                }41                totalArea = (totalArea + width * yLength) % MOD;42            }43 44            int temp_i = i;45            while (temp_i < events.size() && events.get(temp_i)[0] == currentX) {46                int[] event = events.get(temp_i);47                int[] interval = new int[]{event[1], event[2]};48                if (event[3] == 1) {49                    activeIntervals.add(interval);50                } else { // type == -151                    // This removal is O(N)52                    for(int k=0; k<activeIntervals.size(); k++){53                        if(activeIntervals.get(k)[0] == interval[0] && activeIntervals.get(k)[1] == interval[1]){54                            activeIntervals.remove(k);55                            break;56                        }57                    }58                }59                temp_i++;60            }61            i = temp_i;62            lastX = currentX;63        }64 65        return (int) totalArea;66    }67}

• Collect all unique y-coordinates and sort them. This forms the basis for our segment tree.
• Create events (x, y1, y2, type) as in the previous approach and sort them by x-coordinate.
• Build a segment tree over the y-coordinate indices. Each node in the tree will store a count (how many active rectangles cover its interval) and a length (the total covered length within its interval).
• Initialize total_area = 0 and last_x.
• Sweep through the sorted events:
  • For a strip between last_x and current_x, the width is current_x - last_x.
  • The covered height is the length value stored at the root of the segment tree.
  • Add (width * root.length) to total_area.
  • At current_x, process all events. For an 'enter' event, perform a range update on the segment tree to increment the count for its y-interval. For a 'leave' event, decrement the count.
  • After each update, recalculate the length in the affected segment tree nodes. A node's length is its full interval length if its count > 0; otherwise, it's the sum of its children's lengths.
• Return the final total_area.

This is the most efficient approach, building upon the plane sweep algorithm. The bottleneck in the previous approach was calculating the total length of active y-intervals, which took O(N log N) time. We can optimize this calculation to O(log N) using a Segment Tree.

The setup is similar: we create 'enter' and 'leave' events and sort them by their x-coordinate. The key difference lies in how we manage the active y-intervals.

1. Y-Coordinate Discretization: First, we collect all unique y-coordinates from the rectangles and sort them. Let this list be y_coords. The segment tree will be built upon the indices of this list. An interval [y_coords[i], y_coords[i+1]] is a basic segment.

2. Segment Tree Structure: Each node in the segment tree will represent a range of y-intervals, e.g., [y_coords[i], y_coords[j]]. We store two values in each node:

   • count: An integer representing how many rectangles currently cover this entire segment. An update for a rectangle [y1, y2] will affect the count of all segment tree nodes fully contained within the range from y1 to y2.
   • length: The total length of the covered portion within this node's range.

3. Update and Query: As we sweep from left to right:

   • The area of a strip is width * segment_tree_root.length. The length at the root node gives the total covered length on the current sweep line.
   • When we process an event (x, y1, y2, type), we find the indices corresponding to y1 and y2 in our y_coords list. We then perform a range update on the segment tree for this index range. type = +1 for 'enter' increases the count, and type = -1 for 'leave' decreases it.
   • After updating the count for a node, we update its length. If node.count > 0, the entire interval is covered, so node.length is the physical length of its y-range. If node.count == 0, its covered length is the sum of the lengths of its children.

This way, both querying the total length and updating the set of intervals take only O(log N) time, leading to a much faster overall algorithm.

1import java.util.*;2 3class Solution {4    public int rectangleArea(int[][] rectangles) {5        int MOD = 1_000_000_007;6        List<int[]> events = new ArrayList<>();7        TreeSet<Integer> ySet = new TreeSet<>();8 9        for (int[] r : rectangles) {10            events.add(new int[]{r[0], r[1], r[3], 1});11            events.add(new int[]{r[2], r[1], r[3], -1});12            ySet.add(r[1]);13            ySet.add(r[3]);14        }15 16        Collections.sort(events, (a, b) -> a[0] - b[0]);17        List<Integer> yCoords = new ArrayList<>(ySet);18        Map<Integer, Integer> yMap = new HashMap<>();19        for (int i = 0; i < yCoords.size(); i++) {20            yMap.put(yCoords.get(i), i);21        }22 23        int n = yCoords.size();24        long[] length = new long[4 * n];25        int[] count = new int[4 * n];26 27        long totalArea = 0;28        int lastX = events.get(0)[0];29 30        for (int i = 0; i < events.size(); i++) {31            int[] event = events.get(i);32            int curX = event[0];33            long width = curX - lastX;34 35            if (width > 0) {36                totalArea = (totalArea + width * length[1]) % MOD;37            }38 39            int y1_idx = yMap.get(event[1]);40            int y2_idx = yMap.get(event[2]);41            int type = event[3];42 43            update(1, 0, n - 1, y1_idx, y2_idx - 1, type, count, length, yCoords);44            lastX = curX;45        }46 47        return (int) totalArea;48    }49 50    private void update(int node, int start, int end, int l, int r, int val, int[] count, long[] length, List<Integer> yCoords) {51        if (start > r || end < l) {52            return;53        }54        if (l <= start && end <= r) {55            count[node] += val;56        } else {57            int mid = start + (end - start) / 2;58            update(2 * node, start, mid, l, r, val, count, length, yCoords);59            update(2 * node + 1, mid + 1, end, l, r, val, count, length, yCoords);60        }61        62        if (count[node] > 0) {63            length[node] = yCoords.get(end + 1) - yCoords.get(start);64        } else {65            if (start == end) {66                length[node] = 0;67            } else {68                length[node] = length[2 * node] + length[2 * node + 1];69            }70        }71    }72}