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 <= 200rectangles[i].length == 40 <= x1, y1, x2, y2 <= 10^9x1 <= x2y1 <= y2
Hints for Rectangle Area II
Hint 1
Only the distinct x-coordinates and y-coordinates of the corners matter; between consecutive ones nothing changes.
Hint 2
Those coordinates cut the plane into at most 399 × 399 elementary cells, each fully covered or fully uncovered.
Hint 3
Mark the cells each rectangle covers, then add
width × heightof 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
- Collect every
x1, x2into a sorted listxswithout duplicates, and everyy1, y2intoys. - Build a boolean grid
coveredof size|xs| × |ys|; cell(i, j)stands for the box[xs[i], xs[i+1]] × [ys[j], ys[j+1]]. - For each rectangle, find the indices of its corners in
xsandysand mark every cell between them. - 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 % MODJava
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