Vultr DocsLatest Content

Rectangle Area II

Updated on 23 June, 2025
Rectangle Area II header image

Problem Statement

In this challenge, you are provided with a list of rectangles defined in a 2D coordinate system. Each rectangle is represented by an array, [xi1, yi1, xi2, yi2], where (xi1, yi1) and (xi2, yi2) are the coordinates of the bottom-left and top-right corners respectively. The task is to compute the total area covered by all these rectangles. It's important to keep in mind that if any rectangles overlap, the overlapping area should not be counted multiple times in the total. Due to potentially large areas, the result should be provided modulo $10^9 + 7$ to handle large numbers.

Examples

Example 1

Input:

rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]

Output:

6

Explanation:

A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

Example 2

Input:

rectangles = [[0,0,1000000000,1000000000]]

Output:

49

Explanation:

The answer is 1018 modulo (109 + 7), which is 49.

Constraints

  • 1 <= rectangles.length <= 200
  • rectanges[i].length == 4
  • 0 <= xi1, yi1, xi2, yi2 <= 109
  • xi1 <= xi2
  • yi1 <= yi2
  • All rectangles have non zero area.

Approach and Intuition

Given the possibility of overlap among rectangles, a straightforward calculation of summing individual areas won't suffice as it could count overlapping regions multiple times. Here’s a strategic approach to solve the problem:

  1. Understanding the Overlaps: Recognize that overlapping rectangles can complicate the calculation of the area. For instance, when rectangles share common space, this shared area must only be counted once.

  2. Sweep Line Algorithm Using Events:

    • This technique involves processing "events" as we sweep a line (typically vertical) across the plane. Each rectangle contributes two events: one for the left edge (entering event) and one for the right edge (exiting event).
    • Events are sorted primarily by x-coordinates, ensuring processing from left to right. In cases where x-coordinates tie, entering events are prioritized over exiting events to correctly adjust active regions in the line sweep.

  3. Maintaining Active Intervals:

    • Use a data structure (like a balanced binary search tree or a segment tree) to manage active vertical intervals efficiently. This helps in adding, removing, and querying vertical extents of overlapping rectangles as the sweep line progresses.

  4. Calculating Areas:

    • As the sweep line moves from one event to the next, calculate the horizontal width (difference between current and previous x-coordinates). Multiply this width by the combined length of all active vertical intervals to obtain the area between these events.
    • Continually sum these calculated areas while employing modulo operations to handle large results.

By effectively implementing and combining these techniques, you can account for overlaps correctly and efficiently compute the total area covered by the given rectangles.

Solutions

  • Java
  • Python
java 
class Solution {
    public int calculateArea(int[][] rects) {
        int START = 1, END = -1;
        int[][] actions = new int[rects.length * 2][];
        Set<Integer> xCoordinates = new HashSet();
        int index = 0;
        
        for (int[] rect: rects) {
            if ((rect[0] < rect[2]) && (rect[1] < rect[3])) {
                actions[index++] = new int[]{rect[1], START, rect[0], rect[2]};
                actions[index++] = new int[]{rect[3], END, rect[0], rect[2]};
                xCoordinates.add(rect[0]);
                xCoordinates.add(rect[2]);
            }
        }

        Arrays.sort(actions, 0, index, (a, b) -> Integer.compare(a[0], b[0]));

        Integer[] sortedX = xCoordinates.toArray(new Integer[0]);
        Arrays.sort(sortedX);
        Map<Integer, Integer> xIndex = new HashMap();
        for (int i = 0; i < sortedX.length; ++i)
            xIndex.put(sortedX[i], i);

        Segment activeSegments = new Segment(0, sortedX.length - 1, sortedX);
        long result = 0;
        long current_xSum = 0;
        int currentY = actions[0][0];
        
        for (int[] action: actions) {
            if (action == null) break;
            int y = action[0], type = action[1], x1 = action[2], x2 = action[3];
            result += current_xSum * (y - currentY);
            current_xSum = activeSegments.update(xIndex.get(x1), xIndex.get(x2), type);
            currentY = y;
        }

        result %= 1_000_000_007;
        return (int) result;
    }
}

class Segment {
    int start, end;
    Integer[] xValues;
    Segment left, right;
    int count;
    long sum;

    public Segment(int start, int end, Integer[] xValues) {
        this.start = start;
        this.end = end;
        this.xValues = xValues;
        left = null;
        right = null;
        count = 0;
        sum = 0;
    }

    public int midPoint() {
        return start + (end - start) / 2;
    }

    public Segment leftChild() {
        if (left == null) left = new Segment(start, midPoint(), xValues);
        return left;
    }

    public Segment rightChild() {
        if (right == null) right = new Segment(midPoint() + 1, end, xValues);
        return right;
    }

    public long update(int l, int r, int val) {
        if (l >= r) return 0;
        if (start == l && end == r) {
            count += val;
        } else {
            leftChild().update(l, Math.min(midPoint() + 1, r), val);
            rightChild().update(Math.max(midPoint() + 1, l), r, val);
        }

        if (count > 0) sum = xValues[end] - xValues[start];
        else sum = leftChild().sum + rightChild().sum;

        return sum;
    }
}

The provided Java solution computes the total area of multiple rectangles potentially overlapping each other on a 2D plane. The approach uses a line sweep algorithm with segments, enhancing efficiency for potentially large data sets.

  • In the Solution class:

    • calculateArea method begins by initializing several containers and variables to manage the rectangles' coordinates and related events during the line sweep.
    • Each rectangle contributes two events (START and END) which are stored in the actions array and represent entering and leaving a rectangle at certain y-coordinates.
    • These events are sorted primarily by y-coordinate.
    • X-coordinates of the corners are stored in a hash set which is then converted into a sorted array, allowing for indexed management via a hash map.
    • Segment tree structure (activeSegments) is used to maintain and update the coverage of x-intervals as lines are processed.

  • The Segment class:

    • Represents segments of x-coordinates between y-interval changes. Handles updating the coverage of the x-interval efficiently.
    • Supports operations to add or remove coverage of certain x-intervals and calculates the resulting length of covered x-intervals.
    • It handles propagation of segment updates to maintain total coverage and computes sum as needed.

Each event adjusts the current coverage in the Segment structure, multiplying the covered length by the vertical distance moved and adding it to the result. This efficiently accounts for overlapping rectangles by considering rectangle borders along the y-axis, actively modifying the covered x-interval.

The result ensures robust and efficient processing of potentially overlapping intervals without straightforwardly handling each possible overlapping region individually.

  • The final area calculation is taken modulo 1_000_000_007 to handle large outputs and ensure proper integer ranges for competitive programming environments.

This method is optimal for problems involving geometric computations and overlapping intervals, displaying efficient space and time complexity relative to the direct enumeration of each possible overlapping area.

python 
class IntervalNode:
    def __init__(self, low: int, high: int, coord_list: List[int]) -> None:
        self.low, self.high = low, high
        self.sum_total = self.active_count = 0
        self.left_child = self.right_child = None
        self.coord_list = coord_list

    @property
    def midpoint(self):
        return (self.low + self.high) // 2

    @property
    def left(self):
        if not self.left_child:
            self.left_child = IntervalNode(self.low, self.midpoint, self.coord_list)
        return self.left_child

    @property
    def right(self):
        if not self.right_child:
            self.right_child = IntervalNode(self.midpoint, self.high, self.coord_list)
        return self.right_child

    def incremental_update(self, index_low: int, index_high: int, value: int) -> int:
        if index_low >= index_high: return 0
        if self.low == index_low and self.high == index_high:
            self.active_count += value
        else:
            self.left.incremental_update(index_low, min(self.midpoint, index_high), value)
            self.right.incremental_update(max(self.midpoint, index_low), index_high, value)

        if self.active_count > 0:
            self.sum_total = self.coord_list[self.high] - self.coord_list[self.low]
        else:
            self.sum_total = self.left.sum_total + self.right.sum_total

        return self.sum_total

class AreaCalculator:
    def computeArea(self, rectangles: List[List[int]]) -> int:
        ENTRY, EXIT = 1, -1
        events = []
        
        X_coors = set()
        for x1, y1, x2, y2 in rectangles:
            if (x1 < x2) and (y1 < y2):
                events.append((y1, ENTRY, x1, x2))
                events.append((y2, EXIT, x1, x2))
                X_coors.add(x1)
                X_coors.add(x2)
        events.sort()

        X_coors = sorted(X_coors)
        coor_map = {x: i for i, x in enumerate(X_coors)}
        active_intervals = IntervalNode(0, len(X_coors) - 1, X_coors)
        accumulated_area = 0
        previous_y = events[0][0]

        for y, typ, x1, x2 in events:
            accumulated_area += (y - previous_y) * active_intervals.sum_total
            active_intervals.incremental_update(coor_map[x1], coor_map[x2], typ)
            previous_y = y

        return accumulated_area % (10**9 + 7)

The provided Python code computes the area covered by multiple overlapping rectangles using a data structure known as an interval tree. By leveraging the interval tree and a line sweep algorithm, it efficiently calculates the union of the rectangles' areas.

Key aspects of the program include:

  • IntervalNode Class: Represents a node in the interval tree with specific properties and methods.

    • Properties include the range of coordinate indices (low, high), active_count to track overlapping intervals, and sum_total which maintains the total length of intervals covered by active rectangles.
    • Methods include incremental_update to update counts and calculate overlap, dynamically creating child nodes as needed.

  • AreaCalculator Class:

    • computeArea method is responsible for calculating the total area covered by the given rectangles.
    • It initializes intervals based on rectangle coordinates, sorts events for each rectangle's start and end along the y-axis, and maintain a set of unique x-coordinates to handle overlapping efficiently.
    • The method uses a line sweep technique:
      • Sweeps over the y-coordinates of the rectangle events (both ENTRY and EXIT).
      • Between sweeps, it updates the accumulated area based on the product of width (calculated from IntervalNode.sum_total) and the gap in y coordinates between consecutive events.
      • Uses a modulo operation to ensure the result fits within given constraints.

How to use:

  1. Instantiate the AreaCalculator.
  2. Use the computeArea function and pass a list of rectangles in the format [x1, y1, x2, y2] where (x1, y1) and (x2, y2) are the bottom-left and top-right coordinates of the rectangle.
  3. The function outputs the area of the union of the rectangles modulo 10**9 + 7.

Example:

python 
calculator = AreaCalculator()
rectangles = [[1,1,3,3], [2,2,4,4]]
print(calculator.computeArea(rectangles))  # Output will be the area

This program efficiently manages overlapping rectangles and computes the total area covered by these rectangles, using a combination of efficient data structures and algorithmic strategies. It handles the complexities of intervals and overlapping with a sophisticated internal mechanism provided by the IntervalNode's management of active counts and sum totals.

Comments

No comments yet.