Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= yi2Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Segment Tree
[[0,0,2,2],[1,0,2,3],[1,0,3,1]]
[[0,0,1000000000,1000000000]]
separate-squares-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #850: Rectangle Area II
class Node {
int l, r, cnt, length;
}
class SegmentTree {
private Node[] tr;
private int[] nums;
public SegmentTree(int[] nums) {
this.nums = nums;
int n = nums.length - 1;
tr = new Node[n << 2];
for (int i = 0; i < tr.length; ++i) {
tr[i] = new Node();
}
build(1, 0, n - 1);
}
private void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
if (l != r) {
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
}
public void modify(int u, int l, int r, int k) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].cnt += k;
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid) {
modify(u << 1, l, r, k);
}
if (r > mid) {
modify(u << 1 | 1, l, r, k);
}
}
pushup(u);
}
private void pushup(int u) {
if (tr[u].cnt > 0) {
tr[u].length = nums[tr[u].r + 1] - nums[tr[u].l];
} else if (tr[u].l == tr[u].r) {
tr[u].length = 0;
} else {
tr[u].length = tr[u << 1].length + tr[u << 1 | 1].length;
}
}
public int query() {
return tr[1].length;
}
}
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int rectangleArea(int[][] rectangles) {
int n = rectangles.length;
int[][] segs = new int[n << 1][4];
int i = 0;
TreeSet<Integer> ts = new TreeSet<>();
for (var e : rectangles) {
int x1 = e[0], y1 = e[1], x2 = e[2], y2 = e[3];
segs[i++] = new int[] {x1, y1, y2, 1};
segs[i++] = new int[] {x2, y1, y2, -1};
ts.add(y1);
ts.add(y2);
}
Arrays.sort(segs, (a, b) -> a[0] - b[0]);
Map<Integer, Integer> m = new HashMap<>(ts.size());
i = 0;
int[] nums = new int[ts.size()];
for (int v : ts) {
m.put(v, i);
nums[i++] = v;
}
SegmentTree tree = new SegmentTree(nums);
long ans = 0;
for (i = 0; i < segs.length; ++i) {
var e = segs[i];
int x = e[0], y1 = e[1], y2 = e[2], k = e[3];
if (i > 0) {
ans += (long) tree.query() * (x - segs[i - 1][0]);
}
tree.modify(1, m.get(y1), m.get(y2) - 1, k);
}
ans %= MOD;
return (int) ans;
}
}
// Accepted solution for LeetCode #850: Rectangle Area II
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
}
}
# Accepted solution for LeetCode #850: Rectangle Area II
class Node:
def __init__(self):
self.l = self.r = 0
self.cnt = self.length = 0
class SegmentTree:
def __init__(self, nums):
n = len(nums) - 1
self.nums = nums
self.tr = [Node() for _ in range(n << 2)]
self.build(1, 0, n - 1)
def build(self, u, l, r):
self.tr[u].l, self.tr[u].r = l, r
if l != r:
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
def modify(self, u, l, r, k):
if self.tr[u].l >= l and self.tr[u].r <= r:
self.tr[u].cnt += k
else:
mid = (self.tr[u].l + self.tr[u].r) >> 1
if l <= mid:
self.modify(u << 1, l, r, k)
if r > mid:
self.modify(u << 1 | 1, l, r, k)
self.pushup(u)
def pushup(self, u):
if self.tr[u].cnt:
self.tr[u].length = self.nums[self.tr[u].r + 1] - self.nums[self.tr[u].l]
elif self.tr[u].l == self.tr[u].r:
self.tr[u].length = 0
else:
self.tr[u].length = self.tr[u << 1].length + self.tr[u << 1 | 1].length
@property
def length(self):
return self.tr[1].length
class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
segs = []
alls = set()
for x1, y1, x2, y2 in rectangles:
segs.append((x1, y1, y2, 1))
segs.append((x2, y1, y2, -1))
alls.update([y1, y2])
segs.sort()
alls = sorted(alls)
tree = SegmentTree(alls)
m = {v: i for i, v in enumerate(alls)}
ans = 0
for i, (x, y1, y2, k) in enumerate(segs):
if i:
ans += tree.length * (x - segs[i - 1][0])
tree.modify(1, m[y1], m[y2] - 1, k)
ans %= int(1e9 + 7)
return ans
// Accepted solution for LeetCode #850: Rectangle Area II
/**
* [0850] Rectangle Area II
*
* You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the i^th 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 10^9 + 7.
*
* <strong class="example">Example 1:
* <img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/06/rectangle_area_ii_pic.png" style="width: 600px; height: 450px;" />
* 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.
*
* <strong class="example">Example 2:
*
* Input: rectangles = [[0,0,1000000000,1000000000]]
* Output: 49
* Explanation: The answer is 10^18 modulo (10^9 + 7), which is 49.
*
*
* Constraints:
*
* 1 <= rectangles.length <= 200
* rectanges[i].length == 4
* 0 <= xi1, yi1, xi2, yi2 <= 10^9
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/rectangle-area-ii/
// discuss: https://leetcode.com/problems/rectangle-area-ii/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
const MOD: i32 = 1000000007;
impl Solution {
pub fn rectangle_area(rectangles: Vec<Vec<i32>>) -> i32 {
let mut xs = std::collections::BTreeSet::new();
let mut ys = std::collections::BTreeSet::new();
for rec in rectangles.iter() {
xs.insert(rec[0]);
xs.insert(rec[2]);
ys.insert(rec[1]);
ys.insert(rec[3]);
}
// BTreeSet makes sure that all values are sorted
let xs: Vec<i32> = xs.iter().map(|x| *x).collect();
let ys: Vec<i32> = ys.iter().map(|y| *y).collect();
let mut canvas = vec![vec![false; ys.len()]; xs.len()];
let mut area: i32 = 0;
for rec in rectangles.iter() {
let mut xi = xs.binary_search(&rec[0]).unwrap();
for xi in (xi..).take_while(|xi| xs[*xi] != rec[2]) {
let mut yi = ys.binary_search(&rec[1]).unwrap();
for yi in (yi..).take_while(|yi| ys[*yi] != rec[3]) {
if canvas[xi][yi] {
// the pixel is already painted
continue;
}
canvas[xi][yi] = true;
let rec_area = (xs[xi + 1] as i64 - xs[xi] as i64)
* (ys[yi + 1] as i64 - ys[yi] as i64)
% MOD as i64;
area = (area + rec_area as i32) % MOD;
}
}
}
area
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0850_example_1() {
let rectangles = vec![vec![0, 0, 2, 2], vec![1, 0, 2, 3], vec![1, 0, 3, 1]];
let result = 6;
assert_eq!(Solution::rectangle_area(rectangles), result);
}
#[test]
fn test_0850_example_2() {
let rectangles = vec![vec![0, 0, 1000000000, 1000000000]];
let result = 49;
assert_eq!(Solution::rectangle_area(rectangles), result);
}
}
// Accepted solution for LeetCode #850: Rectangle Area II
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #850: Rectangle Area II
// class Node {
// int l, r, cnt, length;
// }
//
// class SegmentTree {
// private Node[] tr;
// private int[] nums;
//
// public SegmentTree(int[] nums) {
// this.nums = nums;
// int n = nums.length - 1;
// tr = new Node[n << 2];
// for (int i = 0; i < tr.length; ++i) {
// tr[i] = new Node();
// }
// build(1, 0, n - 1);
// }
//
// private void build(int u, int l, int r) {
// tr[u].l = l;
// tr[u].r = r;
// if (l != r) {
// int mid = (l + r) >> 1;
// build(u << 1, l, mid);
// build(u << 1 | 1, mid + 1, r);
// }
// }
//
// public void modify(int u, int l, int r, int k) {
// if (tr[u].l >= l && tr[u].r <= r) {
// tr[u].cnt += k;
// } else {
// int mid = (tr[u].l + tr[u].r) >> 1;
// if (l <= mid) {
// modify(u << 1, l, r, k);
// }
// if (r > mid) {
// modify(u << 1 | 1, l, r, k);
// }
// }
// pushup(u);
// }
//
// private void pushup(int u) {
// if (tr[u].cnt > 0) {
// tr[u].length = nums[tr[u].r + 1] - nums[tr[u].l];
// } else if (tr[u].l == tr[u].r) {
// tr[u].length = 0;
// } else {
// tr[u].length = tr[u << 1].length + tr[u << 1 | 1].length;
// }
// }
//
// public int query() {
// return tr[1].length;
// }
// }
//
// class Solution {
// private static final int MOD = (int) 1e9 + 7;
//
// public int rectangleArea(int[][] rectangles) {
// int n = rectangles.length;
// int[][] segs = new int[n << 1][4];
// int i = 0;
// TreeSet<Integer> ts = new TreeSet<>();
// for (var e : rectangles) {
// int x1 = e[0], y1 = e[1], x2 = e[2], y2 = e[3];
// segs[i++] = new int[] {x1, y1, y2, 1};
// segs[i++] = new int[] {x2, y1, y2, -1};
// ts.add(y1);
// ts.add(y2);
// }
// Arrays.sort(segs, (a, b) -> a[0] - b[0]);
// Map<Integer, Integer> m = new HashMap<>(ts.size());
// i = 0;
// int[] nums = new int[ts.size()];
// for (int v : ts) {
// m.put(v, i);
// nums[i++] = v;
// }
//
// SegmentTree tree = new SegmentTree(nums);
// long ans = 0;
// for (i = 0; i < segs.length; ++i) {
// var e = segs[i];
// int x = e[0], y1 = e[1], y2 = e[2], k = e[3];
// if (i > 0) {
// ans += (long) tree.query() * (x - segs[i - 1][0]);
// }
// tree.modify(1, m.get(y1), m.get(y2) - 1, k);
// }
// ans %= MOD;
// return (int) ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.