Practice/Google/Leetcode 850. Rectangle Area II

Leetcode 850. Rectangle Area II

CodingMust

Problem

You are given an array of axis-aligned rectangles on a 2D plane. Each rectangle is represented as [x1, y1, x2, y2] where (x1, y1) is the coordinate of the bottom-left corner and (x2, y2) is the coordinate of the top-right corner.

Calculate the total area covered by all rectangles combined. If rectangles overlap, count the overlapping region only once. Return the answer modulo 10^9 + 7.

Requirements

1. Compute the union area of all rectangles
2. Overlapping regions should be counted exactly once
3. Return the result modulo 10^9 + 7
4. Handle large coordinate values efficiently (up to 10^9)

Constraints

• 1 <= rectangles.length <= 200
• rectangles[i].length == 4
• 0 <= x1 < x2 <= 10^9
• 0 <= y1 < y2 <= 10^9
• Time complexity should be better than O(n² × coordinate_range)
• Space complexity should be reasonable for the input size

Examples

Example 1:

Input: rectangles = [[0, 0, 2, 2], [1, 1, 3, 3]] Output: 7 Explanation: The first rectangle covers area 4, the second covers area 4. They overlap in a 1x1 square (area 1). Total union area = 4 + 4 - 1 = 7.

Example 2:

Input: rectangles = [[0, 0, 1, 1], [2, 2, 3, 3]] Output: 2 Explanation: Two separate 1x1 squares with no overlap. Total area = 1 + 1 = 2.

Example 3:

Input: rectangles = [[0, 0, 1000000000, 1000000000]] Output: 49 Explanation: A single large rectangle with area 10^18. Result modulo 10^9 + 7 = 49.