Rectangle Area II
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 <= 200rectangles[i].length == 40 <= x1 <= x2 <= 10^9and0 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (coordinate compression grid) | O(n³) | O(n²) |
| Optimal (line sweep over x) | O(n²) | O(n) |
1Brute force (coordinate compression grid)
O(n³)Each of the n rectangles can mark up to (2n)² cells.O(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.
- Sort the distinct x values
xsand y valuesys; map each value to its index. - For each rectangle, mark every cell
(i, j)withxs[i]in[x1, x2)andys[j]in[y1, y2). - 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;
}
}class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
MOD = 10**9 + 7
xs = sorted({v for r in rectangles for v in (r[0], r[2])})
ys = sorted({v for r in rectangles for v in (r[1], r[3])})
xi = {v: i for i, v in enumerate(xs)}
yi = {v: j for j, v in enumerate(ys)}
covered = [[False] * len(ys) for _ in xs]
for x1, y1, x2, y2 in rectangles:
for i in range(xi[x1], xi[x2]):
for j in range(yi[y1], yi[y2]):
covered[i][j] = True
area = 0
for i in range(len(xs) - 1):
for j in range(len(ys) - 1):
if covered[i][j]:
area += (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j])
return area % MODclass Solution {
public:
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());
auto idx = [](vector<int>& v, int x) { return (int)(lower_bound(v.begin(), v.end(), x) - v.begin()); };
vector<vector<bool>> covered(xs.size(), vector<bool>(ys.size(), false));
for (auto& r : rectangles) {
for (int i = idx(xs, r[0]); i < idx(xs, r[2]); i++) {
for (int j = idx(ys, r[1]); j < idx(ys, r[3]); j++) covered[i][j] = true;
}
}
long long area = 0;
for (int i = 0; i + 1 < (int)xs.size(); i++) {
for (int j = 0; j + 1 < (int)ys.size(); j++) {
if (covered[i][j]) {
area = (area + (long long)(xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j])) % MOD;
}
}
}
return (int)area;
}
};function rectangleArea(rectangles) {
const MOD = 1000000007n;
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);
const xi = new Map(xs.map((v, i) => [v, i]));
const yi = new Map(ys.map((v, j) => [v, j]));
const covered = xs.map(() => new Array(ys.length).fill(false));
for (const [x1, y1, x2, y2] of rectangles) {
for (let i = xi.get(x1); i < xi.get(x2); i++) {
for (let j = yi.get(y1); j < yi.get(y2); j++) covered[i][j] = true;
}
}
let area = 0n;
for (let i = 0; i + 1 < xs.length; i++) {
for (let j = 0; j + 1 < ys.length; j++) {
if (covered[i][j]) {
area = (area + BigInt(xs[i + 1] - xs[i]) * BigInt(ys[j + 1] - ys[j])) % MOD;
}
}
}
return Number(area);
}2Optimal (line sweep over x)
O(n²)There are 2n events and each one scans and updates O(n) y-segments.O(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).
- Sort the distinct y values
ys;count[j]tells how many active rectangles cover[ys[j], ys[j + 1]). - Build events
(x1, +1, y1, y2)and(x2, -1, y1, y2)and sort them by x. - For each event: compute the covered height (sum of segment lengths with
count[j] > 0), addheight * (x - prevX)modulo 10^9 + 7. - Then apply the event: add its
+1or-1to every segment in[y1, y2), and setprevX = 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;
}
}class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
MOD = 10**9 + 7
ys = sorted({v for r in rectangles for v in (r[1], r[3])})
yi = {v: j for j, v in enumerate(ys)}
events = []
for x1, y1, x2, y2 in rectangles:
events.append((x1, 1, y1, y2))
events.append((x2, -1, y1, y2))
events.sort(key=lambda e: e[0])
count = [0] * len(ys)
area = 0
prev_x = events[0][0]
for x, delta, y1, y2 in events:
height = 0
for j in range(len(ys) - 1):
if count[j] > 0:
height += ys[j + 1] - ys[j]
area = (area + height * (x - prev_x)) % MOD
for j in range(yi[y1], yi[y2]):
count[j] += delta
prev_x = x
return areaclass Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
const long long MOD = 1000000007LL;
vector<int> ys;
for (auto& r : rectangles) { ys.push_back(r[1]); ys.push_back(r[3]); }
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
auto idx = [&](int v) { return (int)(lower_bound(ys.begin(), ys.end(), v) - ys.begin()); };
vector<array<int, 4>> events;
for (auto& r : rectangles) {
events.push_back({r[0], 1, r[1], r[3]});
events.push_back({r[2], -1, r[1], r[3]});
}
sort(events.begin(), events.end(), [](const array<int, 4>& a, const array<int, 4>& b) { return a[0] < b[0]; });
vector<int> count(ys.size(), 0);
long long area = 0;
int prevX = events[0][0];
for (auto& e : events) {
long long height = 0;
for (int j = 0; j + 1 < (int)ys.size(); j++) {
if (count[j] > 0) height += ys[j + 1] - ys[j];
}
area = (area + height * (e[0] - prevX)) % MOD;
for (int j = idx(e[2]); j < idx(e[3]); j++) count[j] += e[1];
prevX = e[0];
}
return (int)area;
}
};function rectangleArea(rectangles) {
const MOD = 1000000007n;
const ys = [...new Set(rectangles.flatMap((r) => [r[1], r[3]]))].sort((a, b) => a - b);
const yi = new Map(ys.map((v, j) => [v, j]));
const events = [];
for (const [x1, y1, x2, y2] of rectangles) {
events.push([x1, 1, y1, y2]);
events.push([x2, -1, y1, y2]);
}
events.sort((a, b) => a[0] - b[0]);
const count = new Array(ys.length).fill(0);
let area = 0n;
let prevX = events[0][0];
for (const [x, delta, y1, y2] of events) {
let height = 0;
for (let j = 0; j + 1 < ys.length; j++) {
if (count[j] > 0) height += ys[j + 1] - ys[j];
}
area = (area + BigInt(height) * BigInt(x - prevX)) % MOD;
for (let j = yi.get(y1); j < yi.get(y2); j++) count[j] += delta;
prevX = x;
}
return Number(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.