Rectangle Area II

Hard
1307.

Rectangle Area II

Rectangle Area II is a hard coding problem on arrays, math and sorting, asked in Amazon, Google and Uber interviews.

Each rectangles[i] = [x1, y1, x2, y2] is an axis-aligned rectangle with bottom-left corner (x1, y1) and top-right corner (x2, y2). Rectangles may overlap, nest, repeat, or be degenerate (zero width or height).

Return the total area of the union of all the rectangles — ground covered by several rectangles counts once. The area can be enormous, so return it modulo 10^9 + 7.

Example 1

Input
rectangles = [[0,0,3,2],[2,1,5,4]]
Output
14
Explanation
6 + 9 minus the shared 1 x 1 square.

Example 2

Input
rectangles = [[0,0,1000000000,1000000000]]
Output
49
Explanation
10^18 mod (10^9 + 7) = 49.

Example 3

Input
rectangles = [[1,1,4,4],[2,2,3,3],[0,5,2,5]]
Output
9
Explanation
The second rectangle lies inside the first and the third has no height.

Constraints

  • 1 <= rectangles.length <= 200
  • rectangles[i].length == 4
  • 0 <= x1, y1, x2, y2 <= 10^9
  • x1 <= x2
  • y1 <= y2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} rectangles
 * @return {number}
 */
var rectangleArea = function(rectangles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rectangle Area II — Solution in Python, Java & C++

Rectangle Area II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and math.

Rectangle Area II is a hard coding problem on arrays, math and sorting, asked in Amazon, Google and Uber interviews.

  • Difficulty: Hard
  • Topics: Arrays, Math, Sorting, Geometry
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each rectangles[i] = [x1, y1, x2, y2] is an axis-aligned rectangle with bottom-left corner (x1, y1) and top-right corner (x2, y2). Rectangles may overlap, nest, repeat, or be degenerate (zero width or height).

Return the total area of the union of all the rectangles — ground covered by several rectangles counts once. The area can be enormous, so return it modulo 10^9 + 7.

Example 1

Input: rectangles = [[0,0,3,2],[2,1,5,4]]
Output: 14
Explanation: 6 + 9 minus the shared 1 x 1 square.

Example 2

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: 10^18 mod (10^9 + 7) = 49.

Example 3

Input: rectangles = [[1,1,4,4],[2,2,3,3],[0,5,2,5]]
Output: 9
Explanation: The second rectangle lies inside the first and the third has no height.

Constraints

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

Hints for Rectangle Area II

  1. Hint 1

    Only the distinct x-coordinates and y-coordinates of the corners matter; between consecutive ones nothing changes.

  2. Hint 2

    Those coordinates cut the plane into at most 399 × 399 elementary cells, each fully covered or fully uncovered.

  3. Hint 3

    Mark the cells each rectangle covers, then add width × height of every marked cell — multiply in 64 bits and reduce modulo 10^9 + 7.

How to solve Rectangle Area II

Coordinate compression: the sorted distinct x- and y-coordinates split the plane into a grid of cells, and every cell is either entirely inside the union or entirely outside it.

Approach

  1. Collect every x1, x2 into a sorted list xs without duplicates, and every y1, y2 into ys.
  2. Build a boolean grid covered of size |xs| × |ys|; cell (i, j) stands for the box [xs[i], xs[i+1]] × [ys[j], ys[j+1]].
  3. For each rectangle, find the indices of its corners in xs and ys and mark every cell between them.
  4. Sum (xs[i+1] - xs[i]) · (ys[j+1] - ys[j]) over the marked cells, reducing modulo 10^9 + 7 after each addition.

Why it works

Every rectangle edge lies on one of the compressed coordinates, so no rectangle boundary passes through the interior of a cell: a cell is either inside a given rectangle or disjoint from its interior. The union is therefore exactly the set of marked cells, the cells do not overlap, and summing their areas counts every covered point once.

Complexity

  • Time — O(n³) — n rectangles each marking up to 2n × 2n cells
  • Space — O(n²)

Pitfalls

  • A single cell can be 10^9 × 10^9 = 10^18, past 32-bit and past JavaScript's exact integers — multiply in 64 bits (or split the multiplication) before reducing.
  • Reduce the modulus only at the end of each addition; the true area itself is not stored anywhere.
  • Degenerate rectangles have equal indices and mark nothing — make sure your loops handle an empty range.

Reference solution

Python

from typing import List

def rectangleArea(rectangles: List[List[int]]) -> int:
    MOD = 10 ** 9 + 7
    xs = sorted(set([r[0] for r in rectangles] + [r[2] for r in rectangles]))
    ys = sorted(set([r[1] for r in rectangles] + [r[3] for r in rectangles]))
    xi = {v: i for i, v in enumerate(xs)}
    yi = {v: i for i, v in enumerate(ys)}
    covered = [[False] * len(ys) for _ in range(len(xs))]
    for x1, y1, x2, y2 in rectangles:
        for i in range(xi[x1], xi[x2]):
            row = covered[i]
            for j in range(yi[y1], yi[y2]):
                row[j] = True
    total = 0
    for i in range(len(xs) - 1):
        w = xs[i + 1] - xs[i]
        row = covered[i]
        for j in range(len(ys) - 1):
            if row[j]:
                total += w * (ys[j + 1] - ys[j])
    return total % MOD

Java

public static int rectangleArea(int[][] rectangles) {
    final long MOD = 1000000007L;
    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 = new int[xSet.size()];
    int k = 0;
    for (int v : xSet) xs[k++] = v;
    int[] ys = new int[ySet.size()];
    k = 0;
    for (int v : ySet) ys[k++] = v;
    boolean[][] covered = new boolean[xs.length][ys.length];
    for (int[] r : rectangles) {
        int a = Arrays.binarySearch(xs, r[0]), b = Arrays.binarySearch(xs, r[2]);
        int c = Arrays.binarySearch(ys, r[1]), d = Arrays.binarySearch(ys, r[3]);
        for (int i = a; i < b; i++)
            for (int j = c; j < d; j++) covered[i][j] = true;
    }
    long total = 0;
    for (int i = 0; i + 1 < xs.length; i++) {
        for (int j = 0; j + 1 < ys.length; j++) {
            if (covered[i][j]) total = (total + (long) (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j])) % MOD;
        }
    }
    return (int) total;
}

C++

int rectangleArea(vector<vector<int>>& rectangles) {
    const long long MOD = 1000000007LL;
    vector<int> xs, ys;
    for (auto& r : rectangles) {
        xs.push_back(r[0]); xs.push_back(r[2]);
        ys.push_back(r[1]); ys.push_back(r[3]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<vector<char>> covered(xs.size(), vector<char>(ys.size(), 0));
    for (auto& r : rectangles) {
        int a = lower_bound(xs.begin(), xs.end(), r[0]) - xs.begin();
        int b = lower_bound(xs.begin(), xs.end(), r[2]) - xs.begin();
        int c = lower_bound(ys.begin(), ys.end(), r[1]) - ys.begin();
        int d = lower_bound(ys.begin(), ys.end(), r[3]) - ys.begin();
        for (int i = a; i < b; i++)
            for (int j = c; j < d; j++) covered[i][j] = 1;
    }
    long long total = 0;
    for (size_t i = 0; i + 1 < xs.size(); i++) {
        for (size_t j = 0; j + 1 < ys.size(); j++) {
            if (covered[i][j]) total = (total + (long long) (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j])) % MOD;
        }
    }
    return (int) total;
}

JavaScript

var rectangleArea = function(rectangles) {
    var MOD = 1000000007;
    var mulMod = function(a, b) {
        var hi = Math.floor(b / 65536), lo = b % 65536;
        return ((a * hi) % MOD * 65536 + a * lo) % MOD;
    };
    var uniq = function(a) {
        a.sort(function(p, q) { return p - q; });
        var out = [];
        for (var i = 0; i < a.length; i++) if (i === 0 || a[i] !== a[i - 1]) out.push(a[i]);
        return out;
    };
    var xs = [], ys = [];
    for (var k = 0; k < rectangles.length; k++) {
        xs.push(rectangles[k][0], rectangles[k][2]);
        ys.push(rectangles[k][1], rectangles[k][3]);
    }
    xs = uniq(xs);
    ys = uniq(ys);
    var xi = new Map(), yi = new Map();
    for (k = 0; k < xs.length; k++) xi.set(xs[k], k);
    for (k = 0; k < ys.length; k++) yi.set(ys[k], k);
    var covered = [];
    for (var i = 0; i < xs.length; i++) covered.push(new Array(ys.length).fill(false));
    for (k = 0; k < rectangles.length; k++) {
        var r = rectangles[k];
        var a = xi.get(r[0]), b = xi.get(r[2]), c = yi.get(r[1]), d = yi.get(r[3]);
        for (i = a; i < b; i++) for (var j = c; j < d; j++) covered[i][j] = true;
    }
    var total = 0;
    for (i = 0; i + 1 < xs.length; i++) {
        for (j = 0; j + 1 < ys.length; j++) {
            if (covered[i][j]) total = (total + mulMod(xs[i + 1] - xs[i], ys[j + 1] - ys[j])) % MOD;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms