Rectangle Area II

Hard Intervals Line Sweep Original on LeetCode

Reported atFlipkart

Rectangle Area II is a hard intervals problem solved with the line sweep pattern. The best approach, optimal (line sweep over x), runs in O(n²) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (coordinate compression grid) up.

Problem

You are given a list of axis-aligned rectangles; rectangles[i] = [x1, y1, x2, y2] has its bottom-left corner at (x1, y1) and its top-right corner at (x2, y2).

Return the total area of the plane covered by at least one rectangle. Area covered by several rectangles is counted only once. The answer can be huge, so return it modulo 10^9 + 7.

Examples

Example 1

Input
rectangles = [[0, 0, 3, 2], [1, 1, 4, 4]]
Output
13
Why
The areas are 6 and 9; they share the 2 × 1 block from (1, 1) to (3, 2), so the union is 6 + 9 - 2 = 13.

Example 2

Input
rectangles = [[0, 0, 4, 4], [1, 1, 2, 3], [4, 0, 5, 1]]
Output
17
Why
The second rectangle lies inside the first (16), and the third only touches it along an edge, adding 1.

Example 3

Input
rectangles = [[0, 0, 1000000000, 1000000000]]
Output
49
Why
The area is 10^18, and 10^18 modulo 10^9 + 7 is 49.

Constraints

  • 1 <= rectangles.length <= 200
  • rectangles[i].length == 4
  • 0 <= x1 <= x2 <= 10^9 and 0 <= y1 <= y2 <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (coordinate compression grid)O(n³)O(n²)
Optimal (line sweep over x)O(n²)O(n)

1Brute force (coordinate compression grid)

TimeO(n³)Each of the n rectangles can mark up to (2n)² cells.
SpaceO(n²)The boolean grid has (2n)² cells.

Collect the distinct x coordinates and y coordinates of all corners and sort them. They split the plane into grid cells, and every rectangle covers a contiguous block of whole cells. Mark the covered cells, then sum width × height of every marked cell, taking the result modulo 10^9 + 7.

  1. Sort the distinct x values xs and y values ys; map each value to its index.
  2. For each rectangle, mark every cell (i, j) with xs[i] in [x1, x2) and ys[j] in [y1, y2).
  3. For every marked cell add (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]) (64-bit) to the answer modulo 10^9 + 7.
class Solution {
    public int rectangleArea(int[][] rectangles) {
        final long MOD = 1_000_000_007L;
        TreeSet<Integer> xSet = new TreeSet<>(), ySet = new TreeSet<>();
        for (int[] r : rectangles) {
            xSet.add(r[0]); xSet.add(r[2]);
            ySet.add(r[1]); ySet.add(r[3]);
        }
        int[] xs = xSet.stream().mapToInt(Integer::intValue).toArray();
        int[] ys = ySet.stream().mapToInt(Integer::intValue).toArray();
        Map<Integer, Integer> xi = new HashMap<>(), yi = new HashMap<>();
        for (int i = 0; i < xs.length; i++) xi.put(xs[i], i);
        for (int j = 0; j < ys.length; j++) yi.put(ys[j], j);
        boolean[][] covered = new boolean[xs.length][ys.length];
        for (int[] r : rectangles) {
            for (int i = xi.get(r[0]); i < xi.get(r[2]); i++) {
                for (int j = yi.get(r[1]); j < yi.get(r[3]); j++) covered[i][j] = true;
            }
        }
        long area = 0;
        for (int i = 0; i + 1 < xs.length; i++) {
            for (int j = 0; j + 1 < ys.length; j++) {
                if (covered[i][j]) {
                    area = (area + (long) (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j])) % MOD;
                }
            }
        }
        return (int) area;
    }
}

2Optimal (line sweep over x)

TimeO(n²)There are 2n events and each one scans and updates O(n) y-segments.
SpaceO(n)The event list and the segment counters are O(n).

Turn every rectangle into two events: at x1 its y-range [y1, y2) starts, at x2 it ends. Sort events by x and sweep. Keep, for every elementary y-segment between consecutive distinct y values, how many active rectangles cover it. Between two consecutive event positions the covered height does not change, so the strip contributes coveredHeight × (x - prevX).

  1. Sort the distinct y values ys; count[j] tells how many active rectangles cover [ys[j], ys[j + 1]).
  2. Build events (x1, +1, y1, y2) and (x2, -1, y1, y2) and sort them by x.
  3. For each event: compute the covered height (sum of segment lengths with count[j] > 0), add height * (x - prevX) modulo 10^9 + 7.
  4. Then apply the event: add its +1 or -1 to every segment in [y1, y2), and set prevX = x.
class Solution {
    public int rectangleArea(int[][] rectangles) {
        final long MOD = 1_000_000_007L;
        TreeSet<Integer> ySet = new TreeSet<>();
        for (int[] r : rectangles) { ySet.add(r[1]); ySet.add(r[3]); }
        int[] ys = ySet.stream().mapToInt(Integer::intValue).toArray();
        Map<Integer, Integer> yi = new HashMap<>();
        for (int j = 0; j < ys.length; j++) yi.put(ys[j], j);

        List<int[]> events = new ArrayList<>();
        for (int[] r : rectangles) {
            events.add(new int[] { r[0], 1, r[1], r[3] });
            events.add(new int[] { r[2], -1, r[1], r[3] });
        }
        events.sort((a, b) -> Integer.compare(a[0], b[0]));

        int[] count = new int[ys.length];
        long area = 0;
        int prevX = events.get(0)[0];
        for (int[] e : events) {
            long height = 0;
            for (int j = 0; j + 1 < ys.length; j++) {
                if (count[j] > 0) height += ys[j + 1] - ys[j];
            }
            area = (area + height * (e[0] - prevX)) % MOD;
            for (int j = yi.get(e[2]); j < yi.get(e[3]); j++) count[j] += e[1];
            prevX = e[0];
        }
        return (int) area;
    }
}

Edge cases to test

  • One rectangle completely inside another
  • Rectangles that only touch along an edge (no double counting, no gap)
  • Zero-width or zero-height rectangles, which add no area
  • Huge coordinates: a single strip can have area up to 10^18, so multiply in 64-bit (or big) integers before taking the modulo
  • Identical rectangles repeated many times

Hints

Hint 1

Only the distinct x and y coordinates of the corners matter. They cut the plane into a grid of at most (2n - 1)² cells.

Hint 2

Each grid cell is either fully covered or not at all, so you can mark cells and sum the areas of the covered ones.

Hint 3

Faster: sweep a vertical line from left to right. Between two consecutive x events the covered height is constant, so the area of that strip is height × width.

FAQ

What is the best time complexity for Rectangle Area II?

Optimal (line sweep over x) runs in O(n²) time and O(n) extra space. There are 2n events and each one scans and updates O(n) y-segments.

Which pattern does Rectangle Area II use?

It is a intervals problem that uses the line sweep pattern. Other problems with the same pattern: Meeting Rooms II, Car Pooling, Employee Free Time.

Is there a brute force solution for Rectangle Area II?

Yes. Brute force (coordinate compression grid) takes O(n³) time and O(n²) space. Collect the distinct x coordinates and y coordinates of all corners and sort them.

Which edge cases should I test for Rectangle Area II?

One rectangle completely inside another; Rectangles that only touch along an edge (no double counting, no gap); Zero-width or zero-height rectangles, which add no area; Huge coordinates: a single strip can have area up to 10^18, so multiply in 64-bit (or big) integers before taking the modulo; Identical rectangles repeated many times.