hard Rectangle Area II

Problem Statement

You have a 2D array of axis-aligned rectangles, where each rectangle is represented as [x_i1, y_i1, x_i2, y_i2]. The coordinates (x_i1, y_i1) are the bottom-left corner and (x_i2, y_i2) are the top-right corner of the rectangle.

Calculate the total area covered by these rectangles. If any areas overlap, they should be counted only once.

Return the total area, and since the answer can be large, return it modulo 10⁹ + 7.

Examples

Example 1

• Input: rectangles = [[0,0,3,3],[2,2,5,5],[1,1,4,4], [1, 2, 3, 3]]
• Expected Output: 19

• Justification: The combined area of all rectangles is 25 as shown in the above image. Overlapping areas are counted only once.

Example 2

• Input: rectangles = [[1,1,3,3],[2,2,4,4],[3,3,5,5]]
• Expected Output: 10

• Justification: The combined area of all rectangles is 10 as shown in the above image. The overlapping areas are counted only once.

Example 3

• Input: rectangles = [[0,0,1000,1000],[0,0,2,2],[1,1,2,2]]
• Expected Output: 1000000
• Justification: Total area covered by all rectangles is 10⁶ modulo (10⁹ + 7), which is 10⁶.

Constraints:

• 1 <= rectangles.length <= 200
• rectanges[i].length == 4
• 0 <= x_i1, y_i1, x_i2, y_i2 <= 109
• x_i1 <= x_i2
• y_i1 <= y_i2

Solution

To solve this problem, we first transform the problem into a series of events to manage the active intervals of x-coordinates. By treating each rectangle as a combination of open and close events at their respective y-coordinates, we can keep track of which parts of the x-axis are currently covered by rectangles as we sweep from the bottom to the top of the y-axis. This method effectively reduces the problem to one-dimensional interval management at any given y-coordinate. By sorting these events and processing them in order, we can maintain an accurate count of the area covered by rectangles using a segment tree.

The segment tree helps efficiently manage the active intervals of x-coordinates by dynamically updating the covered lengths as we encounter new events. By using a segment tree, we can quickly adjust the active intervals and calculate the total covered length of the x-coordinates after each event. This ensures that we only count the overlapping areas once. The overall area is accumulated as the product of the current length of active x-intervals and the difference in y-coordinates between consecutive events. Finally, we return the total area modulo 10^9 + 7 to handle large numbers.

Step-by-Step Algorithm

1. Initialize Constants and Data Structures:

   • Define constants OPEN as 1 and CLOSE as -1 to represent event types.
   • Initialize an array events to store all events (open and close) and a set xCoordinates to store all unique x-coordinates.
   • Initialize an index variable index to keep track of the number of events.

2. Create Events and Collect x-Coordinates:

   • Loop through each rectangle in the input list rectangles.
   • For each rectangle [x1, y1, x2, y2], check if it is valid (i.e., x1 < x2 and y1 < y2).
   • If valid, create two events: an opening event at y1 and a closing event at y3.
     • Add the event [y1, OPEN, x1, x2] to the events array.
     • Add the event [y3, CLOSE, x1, x2] to the events array.
     • Add the x-coordinates x1 and x2 to the xCoordinates set.
   • Increment the index for each added event.

3. Sort Events by y-Coordinate:

   • Sort the events array from index 0 to index-1 based on the y-coordinate using a comparator.

4. Sort x-Coordinates and Create a Mapping:

   • Convert the xCoordinates set to an array xArray and sort it.
   • Create a mapping xIndexMap from each x-coordinate to its index in the sorted xArray.

5. Initialize the Segment Tree:

   • Create an instance of SegmentTree initialized with the range 0 to xArray.length - 1 and the sorted xArray.

6. Process Events:

   • Initialize variables totalArea to accumulate the total area and currentXSum to track the current sum of active x-interval lengths.
   • Set currentY to the y-coordinate of the first event.
   • Loop through each event in the events array:
     • Extract y, eventType, x1, and x2 from the current event.
     • Update totalArea by adding the product of currentXSum and the difference between y and currentY.
     • Update the segment tree by calling segmentTree.update(xIndexMap.get(x1), xIndexMap.get(x2), eventType) and set currentXSum to the result.
     • Update currentY to the current event's y-coordinate.

7. Return the Total Area:

   • Compute the result as totalArea % 1_000_000_007 to handle large numbers.
   • Return the computed result.

Segment Tree Update() Method:

• Initialization:

  • The segment tree is initialized with a range covering the entire x-coordinate index space.
  • Each node in the segment tree keeps track of the start and end of its range, the total length of covered intervals within that range, and child nodes for the left and right halves of the range.

• Updating the Tree:

  • For each update operation with a range [i, j) and a value val:
    • If the range [i, j) is invalid (i.e., i >= j), return 0.
    • If the current node's range matches [i, j), update the node's count by adding val to it.
    • Otherwise, recursively update the left and right child nodes for the appropriate sub-ranges.
  • After updating, recalculate the total length of the current node's covered intervals:
    • If the node's count is greater than 0, set the total length to the difference between the x-coordinates at the node's end and start indices.
    • Otherwise, set the total length to the sum of the total lengths of the left and right child nodes.
  • Return the updated total length for the current node.

Code

import java.util.*;

class Solution {

  public int rectangleArea(int[][] rectangles) {
    // Define constants for event types
    int OPEN = 1,
      CLOSE = -1;

    // Initialize arrays to hold events and x-coordinates
    int[][] events = new int[rectangles.length * 2][];
    Set<Integer> xCoordinates = new HashSet<>();
    int index = 0;

    // Loop through each rectangle to create events and collect x-coordinates
    for (int[] rectangle : rectangles) {
      // Ensure the rectangle is valid (non-degenerate)
      if ((rectangle[0] < rectangle[2]) && (rectangle[1] < rectangle[3])) {
        // Add opening event for the bottom edge of the rectangle
        events[index++] = new int[] {
          rectangle[1],
          OPEN,
          rectangle[0],
          rectangle[2],
        };
        // Add closing event for the top edge of the rectangle
        events[index++] = new int[] {
          rectangle[3],
          CLOSE,
          rectangle[0],
          rectangle[2],
        };
        // Add x-coordinates to the set
        xCoordinates.add(rectangle[0]);
        xCoordinates.add(rectangle[2]);
      }
    }

    // Sort events by y-coordinate to process them from bottom to top
    Arrays.sort(events, 0, index, (a, b) -> Integer.compare(a[0], b[0]));

    // Convert x-coordinates to an array and sort them
    Integer[] xArray = xCoordinates.toArray(new Integer[0]);
    Arrays.sort(xArray);

    // Create a mapping from x-coordinate to its index in the sorted array
    Map<Integer, Integer> xIndexMap = new HashMap<>();
    for (int i = 0; i < xArray.length; ++i) xIndexMap.put(xArray[i], i);

    // Initialize the segment tree to manage active intervals
    SegmentTree segmentTree = new SegmentTree(0, xArray.length - 1, xArray);
    long totalArea = 0;
    long currentXSum = 0;
    int currentY = events[0][0];

    // Process all events to calculate the total area
    for (int[] event : events) {
      if (event == null) break; // Stop if there are no more events
      int y = event[0],
        eventType = event[1],
        x1 = event[2],
        x2 = event[3];
      // Update the total area using the length of active intervals
      totalArea += currentXSum * (y - currentY);
      // Update the active intervals in the segment tree
      currentXSum = segmentTree.update(
        xIndexMap.get(x1),
        xIndexMap.get(x2),
        eventType
      );
      // Move to the next y-coordinate
      currentY = y;
    }

    // Return the total area modulo 10^9 + 7
    totalArea %= 1_000_000_007;
    return (int) totalArea;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Define test cases
    int[][] rectangles1 = {
      { 0, 0, 3, 3 },
      { 2, 2, 5, 5 },
      { 1, 1, 4, 4 },
      { 1, 2, 3, 3 },
    };
    int[][] rectangles2 = { { 1, 1, 3, 3 }, { 2, 2, 4, 4 }, { 3, 3, 5, 5 } };
    int[][] rectangles3 = {
      { 0, 0, 1000000000, 1000000000 },
      { 0, 0, 2, 2 },
      { 1, 1, 2, 2 },
    };

    // Print results for test cases
    System.out.println("Example 1: " + solution.rectangleArea(rectangles1)); // Expected Output: 19
    System.out.println("Example 2: " + solution.rectangleArea(rectangles2)); // Expected Output: 10
    System.out.println("Example 3: " + solution.rectangleArea(rectangles3)); // Expected Output: 49
  }
}

// Segment tree to manage active intervals
class SegmentTree {

  int start, end;
  Integer[] xArray;
  SegmentTree left, right;
  int count;
  long total;

  // Constructor to initialize the segment tree
  public SegmentTree(int start, int end, Integer[] xArray) {
    this.start = start;
    this.end = end;
    this.xArray = xArray;
    this.left = null;
    this.right = null;
    this.count = 0;
    this.total = 0;
  }

  // Calculate the midpoint of the current range
  public int getRangeMid() {
    return start + (end - start) / 2;
  }

  // Get the left child of the segment tree
  public SegmentTree getLeft() {
    if (left == null) left = new SegmentTree(start, getRangeMid(), xArray);
    return left;
  }

  // Get the right child of the segment tree
  public SegmentTree getRight() {
    if (right == null) right = new SegmentTree(getRangeMid(), end, xArray);
    return right;
  }

  // Update the segment tree with new intervals and calculate the total length
  public long update(int i, int j, int val) {
    if (i >= j) return 0; // No range to update
    if (start == i && end == j) {
      count += val; // Update the count of the interval
    } else {
      // Update the left and right children
      getLeft().update(i, Math.min(getRangeMid(), j), val);
      getRight().update(Math.max(getRangeMid(), i), j, val);
    }

    // Calculate the total length of the active intervals
    if (count > 0) total = xArray[end] - xArray[start];
    else total = getLeft().total + getRight().total;

    return total;
  }
}

Complexity Analysis

Time Complexity

The time complexity of this solution is , where N is the number of rectangles. This is because we process all events (2N events) and for each event, we perform updates and queries on the segment tree, which takes time.

Space Complexity

The space complexity is due to the storage requirements for the events, x-coordinates, and the segment tree nodes.