Rectangle Area II

X-sweep with coordinate compression + 1D union

2D sweep line + coordinate compression. Multi-technique composition.

Published Apr 17, 2026

Problem

You're given n axis-aligned rectangles as [x1, y1, x2, y2]. Return the area of their union modulo 1e9 + 7.

Coordinates can be up to 1e9 and rectangles can overlap arbitrarily — integer overflow and naive inclusion–exclusion (2^n terms) are both real hazards.

Input

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

Output

Explanation

Union is an L-shape with area 6. The three rectangles overlap in the central column.

Input

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

Output

Explanation

A single 10^9 × 10^9 square has area 10^18. 10^18 mod (10^9 + 7) = 49.

Intuition

Inclusion–exclusion collapses with n = 200 (2^200 subsets). A sweep line trades the combinatorial explosion for a linear walk over x-strips between consecutive x-coordinates.

Sort all unique x-coordinates x_0 < x_1 < … < x_k. Between x_i and x_{i+1}, the set of rectangles "active" (containing this x-strip) doesn't change. So the area contribution of the strip is (x_{i+1} − x_i) × (union of active y-intervals). Sum over all strips.

Reducing 2D union to 1D union inside each strip is the whole trick. Union of y-intervals on a line is a classic: sort by lower bound, sweep, extend the current interval or flush when a gap appears.

With n ≤ 200, the O(n²) cost per strip × O(n) strips is under 10^7 ops — fast even with the constant factors of interval merging.

Approach

Brute Grid Scan

TimeO(n · C^2)

SpaceO(C^2)

After coordinate compression, stamp each cell of the compressed grid as "covered" if any rectangle contains its midpoint; sum cell areas. C = 2n so the grid is O(n^2) cells; each cell check is O(n). Total O(n^3) — correct but slower. Useful as an oracle for small cases.

impl Solution {
    pub fn rectangle_area(rectangles: Vec<Vec<i32>>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let xs: Vec<i64> = {
            let mut v: Vec<i64> = rectangles.iter().flat_map(|r| [r[0] as i64, r[2] as i64]).collect();
            v.sort_unstable(); v.dedup(); v
        };
        let ys: Vec<i64> = {
            let mut v: Vec<i64> = rectangles.iter().flat_map(|r| [r[1] as i64, r[3] as i64]).collect();
            v.sort_unstable(); v.dedup(); v
        };
        let mut total: i64 = 0;
        for xw in xs.windows(2) {
            for yw in ys.windows(2) {
                let (x1, x2) = (xw[0], xw[1]);
                let (y1, y2) = (yw[0], yw[1]);
                let covered = rectangles.iter().any(|r| {
                    (r[0] as i64) <= x1 && (r[2] as i64) >= x2
                        && (r[1] as i64) <= y1 && (r[3] as i64) >= y2
                });
                if covered {
                    total = (total + (x2 - x1) % MOD * ((y2 - y1) % MOD)) % MOD;
                }
            }
        }
        total as i32
    }
}

Rust · runnable

function rectangleArea(rectangles: number[][]): number {
  const MOD = 1_000_000_007n;
  const xs = [...new Set(rectangles.flatMap((r) => [r[0], r[2]]))].sort((a, b) => a - b);
  const ys = [...new Set(rectangles.flatMap((r) => [r[1], r[3]]))].sort((a, b) => a - b);
  let total = 0n;
  for (let i = 0; i + 1 < xs.length; i++) {
    for (let j = 0; j + 1 < ys.length; j++) {
      const [x1, x2, y1, y2] = [xs[i], xs[i + 1], ys[j], ys[j + 1]];
      if (rectangles.some((r) => r[0] <= x1 && r[2] >= x2 && r[1] <= y1 && r[3] >= y2)) {
        total = (total + BigInt(x2 - x1) * BigInt(y2 - y1)) % MOD;
      }
    }
  }
  return Number(total);
}

TypeScript · runnable

X-Sweep + 1D Union

TimeO(n^2 log n)

SpaceO(n)

Recommended

Compress x-coordinates. Collect every x1 and x2 into xs, sort + dedup.
For each x-strip [xs[i], xs[i+1]]:
- Collect every rectangle whose x1 ≤ xs[i] and x2 ≥ xs[i+1] (it spans the strip).
- Sort their (y1, y2) intervals and union-merge: walk the sorted list, extend or flush.
- Multiply strip width by covered y-length and add modulo 1e9 + 7.
Watch overflow. Widths and lengths fit in i64; the product also fits in i64 as long as each factor is pre-modded. Keep the multiplication in i64 and apply MOD after.

impl Solution {
    pub fn rectangle_area(rectangles: Vec<Vec<i32>>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut xs: Vec<i64> =
            rectangles.iter().flat_map(|r| [r[0] as i64, r[2] as i64]).collect();
        xs.sort_unstable();
        xs.dedup();

        let mut total: i64 = 0;
        for w in xs.windows(2) {
            let (x1, x2) = (w[0], w[1]);

            let mut ys: Vec<(i64, i64)> = rectangles
                .iter()
                .filter(|r| (r[0] as i64) <= x1 && (r[2] as i64) >= x2)
                .map(|r| (r[1] as i64, r[3] as i64))
                .collect();
            if ys.is_empty() { continue; }
            ys.sort_unstable();

            let mut covered: i64 = 0;
            let (mut lo, mut hi) = ys[0];
            for &(a, b) in &ys[1..] {
                if a > hi {
                    covered += hi - lo;
                    lo = a;
                    hi = b;
                } else {
                    hi = hi.max(b);
                }
            }
            covered += hi - lo;

            total = (total + ((x2 - x1) % MOD) * (covered % MOD) % MOD) % MOD;
        }
        total as i32
    }
}

Rust · runnable

function rectangleArea(rectangles: number[][]): number {
  const MOD = 1_000_000_007n;
  const xs = Array.from(new Set(rectangles.flatMap((r) => [r[0], r[2]]))).sort(
    (a, b) => a - b
  );

  let total = 0n;
  for (let i = 0; i + 1 < xs.length; i++) {
    const x1 = xs[i];
    const x2 = xs[i + 1];

    const ys: Array<[number, number]> = rectangles
      .filter((r) => r[0] <= x1 && r[2] >= x2)
      .map((r) => [r[1], r[3]]);
    if (ys.length === 0) continue;
    ys.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    let covered = 0;
    let [lo, hi] = ys[0];
    for (let k = 1; k < ys.length; k++) {
      const [a, b] = ys[k];
      if (a > hi) { covered += hi - lo; lo = a; hi = b; }
      else if (b > hi) hi = b;
    }
    covered += hi - lo;

    total = (total + (BigInt(x2 - x1) * BigInt(covered)) % MOD) % MOD;
  }
  return Number(total);
}

TypeScript · runnable

Trace

On [[0,0,2,2], [1,0,2,3], [1,0,3,1]]:

strip [x1, x2]	active rects (y-intervals)	union length	strip area
[0, 1]	[(0, 2)]	2	2
[1, 2]	[(0, 2), (0, 3), (0, 1)] → union (0, 3)	3	3
[2, 3]	[(0, 1)]	1	1

Total = 2 + 3 + 1 = 6.

Edge cases

Zero-area rectangles (x1 == x2 or y1 == y2) — drop from the input before sweeping, or they add nothing and the filter handles them silently.
Nested rectangles — smaller one never becomes the active-y representative; 1D union merges it cleanly.
Touching edges (x2_a == x1_b) — strip width x2 − x1 = 0 for the closed boundary; coord compression handles this correctly.
Modular overflow — pre-mod each factor before multiplication. i64 can hold (1e9 + 7) × (1e9 + 7) ≈ 10^18, well under i64::MAX ≈ 9.2 × 10^18, but i32 cannot — never compute with i32 intermediate.

Takeaway

Sweep + compress + reduce 2D to 1D is the universal template for axis-aligned geometry: union area, max overlapping rectangles, staircase skylines (218), kinetic range queries. The only decision per problem is which 1D structure the active set needs (interval merge here, multiset in 218, segment tree in 218 variants with updates).

Mod-arithmetic + 1e9 coordinates is a silent but common trap — keep all intermediate math in 64 bits.

Hard#84

Largest Rectangle in Histogram

THE canonical mono stack problem. Must solve in under 15 minutes.

Hard#85

Maximal Rectangle

Row-by-row histogram heights, then apply #84 per row.

Hard#218

The Skyline Problem

Sweep line + ordered multiset. Compose techniques under pressure.