850. Rectangle Area II

Description

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 109 + 7.

 

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

 

Solutions

Solution: Line Sweep

• Time complexity: O(n²logn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[][]} rectangles
 * @return {number}
 */
const rectangleArea = function (rectangles) {
  const MODULO = BigInt(10 ** 9 + 7);
  const events = [];

  for (const [x1, y1, x2, y2] of rectangles) {
    events.push({ x: x1, y1, y2, type: 'start' }, { x: x2, y1, y2, type: 'end' });
  }
  events.sort((a, b) => a.x - b.x);

  const pairsY = [];
  let prevX = 0;
  let result = 0n;

  const getHeight = () => {
    let prevY = 0;
    let height = 0;

    for (const { y1, y2 } of pairsY) {
      prevY = Math.max(y1, prevY);
      if (prevY >= y2) continue;

      height += y2 - prevY;
      prevY = y2;
    }
    return height;
  };

  for (const { x, y1, y2, type } of events) {
    if (x > prevX) {
      const width = x - prevX;
      const height = getHeight();
      const area = (BigInt(width) * BigInt(height)) % MODULO;

      result = (result + area) % MODULO;
      prevX = x;
    }
    if (type === 'start') {
      pairsY.push({ y1, y2 });
      pairsY.sort((a, b) => a.y1 - b.y1);
      continue;
    }
    const index = pairsY.findIndex(pairs => pairs.y1 === y1 && pairs.y2 === y2);

    pairsY.splice(index, 1);
  }
  return result;
};