Rectangle Area II solution and explanation
Google
9 more videos on this problem
Rectangle Area II | Geometry | Maths | Line Sweep | 850 LeetCode | Day 22CodeWithSunny · 22:11 · 7K views
Leetcode 850 Rectangle Area IIRen Zhang · 25:08 · 4K views
LeetCode 850. Rectangle Area IIHappy Coding · 39:16 · 4K views
850. Rectangle Area II (Leetcode Hard)Programming Live with Larry · 33:12 · 1K views
LeetCode 850. Rectangle Area IIDaniel Tech · 22:33 · 1K views
Daily Leetcode #509: Aug 22, 2021 - 850. Rectangle Area IIProgramming Live with Larry · 25:49 · 1K views
【每日一题】LeetCode 850. Rectangle Area IIHuifeng Guan · 47:29 · 1K views
小Z解题 | LeetCode 850 Rectangle Area IIcoderZ · 23:37 · 1K views
Leetcode 850. Rectangle Area II (sweep line idea)LetsCode · 19:51 · 700 views
850. Rectangle Area IIJust Coding, with Jie · 23:11 · 222 views
The problem
You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.
Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.
Return the total area. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] Output: 6 Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture. From (1,1) to (2,2), the green and red rectangles overlap. From (1,0) to (2,3), all three rectangles overlap.
Example 2:
Input: rectangles = [[0,0,1000000000,1000000000]] Output: 49 Explanation: The answer is 1018 modulo (109 + 7), which is 49.
Constraints:
1 <= rectangles.length <= 200rectanges[i].length == 40 <= xi1, yi1, xi2, yi2 <= 109xi1 <= xi2yi1 <= yi2- All rectangles have non zero area.
Approach overview
Problem Overview: Given multiple axis-aligned rectangles, compute the total area covered by them. Overlapping regions must be counted only once. Coordinates can be large, so the result is typically returned modulo 1e9+7. The challenge is efficiently handling overlapping intervals across many rectangles.
Approach 1: Line Sweep Using Event Sorting (O(n log n) time, O(n) space)
This approach treats every rectangle edge as an event in a vertical line sweep. For each rectangle, create two events: entering at x1 and leaving at x2. As you sweep from left to right, maintain active y-intervals and compute their merged length. The area added between two x-coordinates equals the merged vertical coverage multiplied by the horizontal distance moved. Maintaining intervals typically requires sorting and merging, giving O(n log n) complexity.
Approach 2: Inclusion-Exclusion Principle (O(n^2) time, O(1) extra space)
The inclusion-exclusion idea computes rectangle areas individually and subtracts pairwise overlaps. For two rectangles, compute the intersection region and subtract it from the sum of their areas. Extending this logic to multiple rectangles requires careful overlap handling and quickly becomes quadratic or worse. This method demonstrates the overlap concept but does not scale well for large inputs.
Approach 3: Scanline with Segment Tree (O(n log n) time, O(n) space)
This is the most robust solution and commonly expected in interviews. After sorting x-events, compress all unique y coordinates and maintain coverage counts in a segment tree. Each node tracks how much vertical length is currently covered. When processing an event, update the interval [y1, y2) with +1 or -1. The tree instantly returns the total active vertical length, allowing you to compute area contribution between consecutive x positions efficiently.
Approach 4: Line Sweeping with Interval Addition (O(n log n) time, O(n) space)
This variant keeps active intervals in an ordered structure such as a balanced tree or ordered set. When rectangles start or end, intervals are inserted or removed. The active intervals are merged to calculate the current vertical coverage. Compared to the segment tree method, this implementation is simpler but requires careful merging logic and can have higher constant factors.
Recommended for interviews: The scanline with segment tree approach. A basic sweep-line explanation shows you understand how overlapping areas accumulate, but the segment tree version demonstrates strong algorithmic design and efficient interval aggregation. Most competitive programming and system-level interview solutions use this pattern.
Approach 1: Approach 1: Line Sweep Using Event Sorting
This approach involves treating rectangle edges as events (start and end), which we can sort and process sequentially. By sweeping across the x-axis and using a data structure, like Segment Tree or Balance Tree, to merge y-intervals, we can efficiently calculate the union area of rectangles.
def rectangleArea(rectangles):
MOD = 10**9 + 7
OPEN, CLOSE = 1, -1
events = []
for x1, y1, x2, y2 in rectangles:
events.append((x1, OPEN, y1, y2))
events.append((x2, CLOSE, y1, y2))
events.sort()
def add(intervals, y1, y2):
added_intervals = []
new_interval = [y1, y2]
for i, (a, b) in enumerate(intervals):
if b < y1 or y2 < a:
added_intervals.append([a, b])
else:
new_interval = [min(a, new_interval[0]), max(b, new_interval[1])]
added_intervals.append(new_interval)
return added_intervals
def measure(intervals):
return sum(y2 - y1 for y1, y2 in intervals)
curr_y_intervals = []
last_x = events[0][0]
area = 0
for x, typ, y1, y2 in events:
area += measure(curr_y_intervals) * (x - last_x)
if typ == OPEN:
curr_y_intervals = add(curr_y_intervals, y1, y2)
else:
curr_y_intervals.remove([y1, y2])
curr_y_intervals.sort()
last_x = x
return area % MODThe solution uses a line sweep algorithm where rectangles are decomposed into events indicating if a horizontal segment is starting or ending. These events are sorted by the x-coordinate and processed to update the active intervals on the y-axis. A helper function manages merging y-intervals actively covered, calculating the cumulative area exposed over the previous segment width.
Time Complexity: O(N^2 log N), where N is the number of rectangles. Sorting events takes O(N log N), and updating y-interval intervals can be up to O(N) operations for each event.
Space Complexity: O(N) for storing events and active intervals structures.
Approach 2: Approach 2: Inclusion-Exclusion Principle
This approach involves using the inclusion-exclusion principle to calculate the area by adding all single rectangle areas and subtracting all pairwise overlaps calculated recursively. The approach is computationally intensive for the direct calculation but less error-prone for conceptual integrity.
import java.util.*;
public class RectangleAreaII {
public int rectangleArea(int[][] rectangles) {
int MOD = 1000000007;
List<Event> events = new ArrayList<>();
for (int[] rec : rectangles) {
events.add(new Event(rec[0], rec[1], rec[3], 1));
events.add(new Event(rec[2], rec[1], rec[3], -1));
}
events.sort(Comparator.comparingInt(a -> a.x));
TreeMap<Integer, Integer> active = new TreeMap<>();
long sum = 0, last_x = 0, last_y_sum = 0;
for (Event event : events) {
long x = event.x, type = event.type, y1 = event.y1, y2 = event.y2;
sum = (sum + last_y_sum * (x - last_x)) % MOD;
last_y_sum = 0;
if (type == 1) {
active.put(y1, active.getOrDefault(y1, 0) + type);
active.put(y2, active.getOrDefault(y2, 0) - type);
} else {
active.put(y1, active.getOrDefault(y1, 0) + type);
active.put(y2, active.getOrDefault(y2, 0) - type);
}
int prev = -1;
int count = 0;
for (Map.Entry<Integer, Integer> entry : active.entrySet()) {
if (count > 0) {
last_y_sum += entry.getKey() - prev;
}
count += entry.getValue();
prev = entry.getKey();
}
last_x = x;
}
return (int) sum;
}
class Event {
int x, y1, y2, type;
Event(int x, int y1, int y2, int type) {
this.x = x;
this.y1 = y1;
this.y2 = y2;
this.type = type;
}
}
}This Java implementation uses a TreeMap to keep track of active y-intervals, adding or removing intervals based on the type of event being processed. The expansion of the x-coordinate determines how much additional area to count between events. The TreeMap simplifies the merging and tracking of overlapping y-intervals.
Time Complexity: O(N log N), where the log component comes from interval set operations inherent in TreeMap.
Space Complexity: O(N), mainly for storing events and active structures.
Approach 3: Approach 1: Scanline with Segment Tree
This approach uses the scanline technique combined with a segment tree to handle the union of rectangles. The scanline approach will treat each x-coordinate boundary as an event, i.e., where a rectangle starts or ends. These events allow efficient checking with a segment tree, which tracks active y-intervals.
class SegmentTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (2 * n)
self.lazy = [0] * (2 * n)
def update(self, start, end, value, node, node_start, node_end):
if self.lazy[node] != 0:
self.tree[node] += (node_end - node_start + 1) * self.lazy[node]
if node_start != node_end: # not a leaf node
self.lazy[node * 2 + 1] += self.lazy[node]
self.lazy[node * 2 + 2] += self.lazy[node]
self.lazy[node] = 0
if start > node_end or end < node_start:
return
if start <= node_start and node_end <= end:
self.tree[node] += (node_end - node_start + 1) * value
if node_start != node_end:
self.lazy[node * 2 + 1] += value
self.lazy[node * 2 + 2] += value
return
mid = (node_start + node_end) // 2
self.update(start, end, value, 2 * node + 1, node_start, mid)
self.update(start, end, value, 2 * node + 2, mid + 1, node_end)
self.tree[node] = self.tree[node * 2 + 1] + self.tree[node * 2 + 2]
def query(self):
return self.tree[0]
def rectangleArea(rectangles):
MOD = 10**9 + 7
events = []
y_coords = set()
for x1, y1, x2, y2 in rectangles:
events.append((x1, 1, y1, y2)) # entering, left boundary
events.append((x2, -1, y1, y2)) # leaving, right boundary
y_coords.update([y1, y2])
events.sort()
sorted_y = sorted(y_coords)
y_index = {v: i for i, v in enumerate(sorted_y)}
tree = SegmentTree(len(sorted_y))
current_x = events[0][0]
area = 0
for x, typ, y1, y2 in events:
area += tree.query() * (x - current_x)
area %= MOD
current_x = x
tree.update(y_index[y1], y_index[y2] - 1, typ, 0, 0, len(sorted_y) - 1)
return areaclass SegmentTree {
constructor(n) {
this.n = n;
this.tree = Array(2 * n).fill(0);
this.lazy = Array(2 * n).fill(0);
}
update(start, end, value, node, nodeStart, nodeEnd) {
if (this.lazy[node] !== 0) {
this.tree[node] += (nodeEnd - nodeStart + 1) * this.lazy[node];
if (nodeStart !== nodeEnd) {
this.lazy[node * 2 + 1] += this.lazy[node];
this.lazy[node * 2 + 2] += this.lazy[node];
}
this.lazy[node] = 0;
}
if (start > nodeEnd || end < nodeStart) {
return;
}
if (start <= nodeStart && nodeEnd <= end) {
this.tree[node] += (nodeEnd - nodeStart + 1) * value;
if (nodeStart !== nodeEnd) {
this.lazy[node * 2 + 1] += value;
this.lazy[node * 2 + 2] += value;
}
return;
}
const mid = Math.floor((nodeStart + nodeEnd) / 2);
this.update(start, end, value, 2 * node + 1, nodeStart, mid);
this.update(start, end, value, 2 * node + 2, mid + 1, nodeEnd);
this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
}
query() {
return this.tree[0];
}
}
function rectangleArea(rectangles) {
const MOD = 1e9 + 7;
const events = [];
const yCoords = new Set();
for (const [x1, y1, x2, y2] of rectangles) {
events.push([x1, 1, y1, y2]);
events.push([x2, -1, y1, y2]);
yCoords.add(y1);
yCoords.add(y2);
}
events.sort((a, b) => a[0] - b[0]);
const sortedY = Array.from(yCoords).sort((a, b) => a - b);
const yIndex = new Map(sortedY.map((v, i) => [v, i]));
const tree = new SegmentTree(sortedY.length);
let currentX = events[0][0];
let area = 0;
for (const [x, typ, y1, y2] of events) {
area += tree.query() * (x - currentX);
area %= MOD;
currentX = x;
tree.update(yIndex.get(y1), yIndex.get(y2) - 1, typ, 0, 0, sortedY.length - 1);
}
return area;
}We define a Segment Tree to manage y-coordinates, offering efficient updates for overlapping segments and interval covering. We iterate over event points in sorted order, updating the segment tree for each x-coordinate while calculating the area contribution to the result. Using modulo operation keeps the result scaled within bounds.
Time complexity: O(N log N), where N is the number of events. This arises from sorting the events and using a segment tree for dynamic interval management.
Space complexity: O(N), for storing sorted y-coordinates and constructing the segment tree.
Approach 4: Approach 2: Line Sweeping with Interval Addition
In this approach, we handle the vertical lines or events by consolidating intervals along the x-direction using coordinate compression. The active intervals along the y-axis are populated dynamically as the events are processed. Unlike a Segment Tree, this approach uses a simpler interval tracking to combine overlapping y-segments.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.TreeMap;
class Solution {
public int rectangleArea(int[][] rectangles) {
final int MOD = 1_000_000_007;
List<int[]> events = new ArrayList<>();
HashSet<Integer> yCoords = new HashSet<>();
for (int[] rect : rectangles) {
events.add(new int[]{rect[0], rect[1], rect[3], 1});
events.add(new int[]{rect[2], rect[1], rect[3], -1});
yCoords.add(rect[1]);
yCoords.add(rect[3]);
}
events.sort((a, b) -> Integer.compare(a[0], b[0]));
List<Integer> sortedY = new ArrayList<>(yCoords);
sortedY.sort(Integer::compareTo);
TreeMap<Integer, Integer> yIndex = new TreeMap<>();
for (int i = 0; i < sortedY.size(); i++) {
yIndex.put(sortedY.get(i), i);
}
int[] count = new int[sortedY.size() - 1];
int currentX = events.get(0)[0];
long area = 0;
for (int[] event : events) {
int x = event[0], y1 = event[1], y2 = event[2], type = event[3];
long lengthSum = 0;
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
lengthSum += sortedY.get(i + 1) - sortedY.get(i);
}
}
area = (area + lengthSum * (x - currentX)) % MOD;
currentX = x;
for (int i = yIndex.get(y1); i < yIndex.get(y2); i++) {
count[i] += type;
}
}
return (int) area;
}
}#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
class Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
const int MOD = 1e9+7;
vector<tuple<int, int, int, int>> events;
set<int> y_coords;
for (const auto& rect : rectangles) {
events.emplace_back(rect[0], 1, rect[1], rect[3]);
events.emplace_back(rect[2], -1, rect[1], rect[3]);
y_coords.insert(rect[1]);
y_coords.insert(rect[3]);
}
sort(events.begin(), events.end());
vector<int> sorted_y(y_coords.begin(), y_coords.end());
map<int, int> y_map;
for (int i = 0; i < sorted_y.size(); ++i) {
y_map[sorted_y[i]] = i;
}
vector<int> count(sorted_y.size() - 1, 0);
int currentX = get<0>(events[0]);
long long area = 0;
for (const auto& [x, type, y1, y2] : events) {
long long eventWidth = x - currentX;
long long coveredY = 0;
for (int i = 0; i < count.size(); i++) {
if (count[i] > 0) {
coveredY += sorted_y[i + 1] - sorted_y[i];
}
}
area = (area + eventWidth * coveredY) % MOD;
currentX = x;
for (int i = y_map[y1]; i < y_map[y2]; ++i) {
count[i] += type;
}
}
return area;
}
};This approach defines events across x-coordinates, adjusting interval coverage along the y-axis using count to handle rectangle entry and exits succinctly. By employing coordinate compression and a simple interval logic, it systematically accumulates the total covered area.
Time complexity: O(N log N), given the sorting of events and y-coordinates.
Space complexity: O(N), for event storage and y-indices tracking.
Approach 5: Default Approach
func rectangleArea(rectangles [][]int) int {
var mod int = 1e9 + 7
segs := [][]int{}
alls := map[int]bool{}
for _, e := range rectangles {
x1, y1, x2, y2 := e[0], e[1], e[2], e[3]
segs = append(segs, []int{x1, y1, y2, 1})
segs = append(segs, []int{x2, y1, y2, -1})
alls[y1] = true
alls[y2] = true
}
nums := []int{}
for v := range alls {
nums = append(nums, v)
}
sort.Ints(nums)
sort.Slice(segs, func(i, j int) bool { return segs[i][0] < segs[j][0] })
m := map[int]int{}
for i, v := range nums {
m[v] = i
}
tree := newSegmentTree(nums)
ans := 0
for i, e := range segs {
x, y1, y2, k := e[0], e[1], e[2], e[3]
if i > 0 {
ans += tree.query() * (x - segs[i-1][0])
ans %= mod
}
tree.modify(1, m[y1], m[y2]-1, k)
}
return ans
}
type node struct {
l int
r int
cnt int
length int
}
type segmentTree struct {
tr []*node
nums []int
}
func newSegmentTree(nums []int) *segmentTree {
n := len(nums) - 1
tr := make([]*node, n<<2)
for i := range tr {
tr[i] = &node{}
}
t := &segmentTree{tr, nums}
t.build(1, 0, n-1)
return t
}
func (t *segmentTree) build(u, l, r int) {
t.tr[u].l, t.tr[u].r = l, r
if l == r {
return
}
mid := (l + r) >> 1
t.build(u<<1, l, mid)
t.build(u<<1|1, mid+1, r)
}
func (t *segmentTree) modify(u, l, r, k int) {
if t.tr[u].l >= l && t.tr[u].r <= r {
t.tr[u].cnt += k
} else {
mid := (t.tr[u].l + t.tr[u].r) >> 1
if l <= mid {
t.modify(u<<1, l, r, k)
}
if r > mid {
t.modify(u<<1|1, l, r, k)
}
}
t.pushup(u)
}
func (t *segmentTree) query() int {
return t.tr[1].length
}
func (t *segmentTree) pushup(u int) {
if t.tr[u].cnt > 0 {
t.tr[u].length = t.nums[t.tr[u].r+1] - t.nums[t.tr[u].l]
} else if t.tr[u].l == t.tr[u].r {
t.tr[u].length = 0
} else {
t.tr[u].length = t.tr[u<<1].length + t.tr[u<<1|1].length
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Line Sweep Using Event Sorting | Time Complexity: O(N^2 log N), where N is the number of rectangles. Sorting events takes O(N log N), and updating y-interval intervals can be up to O(N) operations for each event. |
| Approach 2: Inclusion-Exclusion Principle | Time Complexity: O(N log N), where the log component comes from interval set operations inherent in TreeMap. |
| Approach 1: Scanline with Segment Tree | Time complexity: O(N log N), where N is the number of events. This arises from sorting the events and using a segment tree for dynamic interval management. |
| Approach 2: Line Sweeping with Interval Addition | Time complexity: O(N log N), given the sorting of events and y-coordinates. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inclusion-Exclusion Principle | O(n^2) | O(1) | Conceptual understanding of overlapping rectangles or very small input sizes |
| Line Sweep with Event Sorting | O(n log n) | O(n) | General rectangle union problems where intervals can be merged dynamically |
| Scanline with Segment Tree | O(n log n) | O(n) | Best scalable solution for large inputs and common in competitive programming |
| Line Sweeping with Interval Addition | O(n log n) | O(n) | When using ordered sets or balanced trees to maintain active intervals |
Frequently asked questions
Is Rectangle Area II easy or hard?
Rectangle Area II is classified as a hard problem because it combines multiple advanced techniques: line sweep, interval management, coordinate compression, and segment trees. Efficient handling of overlapping regions requires careful event processing and data structure design.
Rectangle Area II Python/Java solution
Python solutions typically implement a sweep line with coordinate compression and a segment tree or interval merging structure. Java implementations often use a segment tree for interval coverage updates during the sweep. Both achieve O(n log n) time complexity.
How to solve Rectangle Area II in O(n log n)?
Create sweep events for rectangle start and end edges along the x-axis. Compress y-coordinates and maintain coverage counts in a segment tree. As the sweep moves between x positions, multiply the covered y-length by the x-distance traveled to accumulate area. Each update and query takes O(log n), producing an overall O(n log n) algorithm.
What is the best approach for Rectangle Area II?
The most reliable approach is a line sweep combined with a segment tree. Sort rectangle edges by x-coordinate and maintain active y-interval coverage in a segment tree. Each sweep step multiplies the horizontal distance moved by the currently covered vertical length. This runs in O(n log n) time and handles large coordinate ranges efficiently.
Is Rectangle Area II asked at Google/Amazon/Meta?
Rectangle union and sweep-line problems appear frequently in interviews at companies like Google, Meta, and Amazon. Variants involving interval coverage, skyline problems, and rectangle intersections test understanding of line sweep and segment tree techniques.
What data structure is used in Rectangle Area II?
The most common implementation uses a segment tree combined with coordinate compression. Some variants also maintain active intervals with an ordered set or balanced tree while performing a line sweep across rectangle edges.
What is the time complexity of Rectangle Area II?
The optimal solution runs in O(n log n) time. Sorting rectangle events takes O(n log n), and each update to the segment tree during the sweep also costs O(log n). Overall space complexity is O(n) for storing events and compressed coordinates.