LeetCode 223: Rectangle Area (Inclusion-Exclusion with Overlap Width/Height)
LeetCode 223GeometryMathInclusion-ExclusionToday we solve LeetCode 223 - Rectangle Area.
Source: https://leetcode.com/problems/rectangle-area/
English
Problem Summary
Given two axis-aligned rectangles A(ax1, ay1, ax2, ay2) and B(bx1, by1, bx2, by2), return the total covered area. If they overlap, the overlap should be counted only once.
Key Insight
Use inclusion-exclusion: total area = area(A) + area(B) - overlap(A, B). The overlap area can be computed from 1D projections on x/y axes.
Brute Force and Limitations
A grid simulation over coordinate cells is possible in theory, but impossible in practice because coordinates can be very large. Geometry formulas are required.
Optimal Algorithm Steps
1) Compute each rectangle area separately.
2) Compute overlap width: max(0, min(ax2, bx2) - max(ax1, bx1)).
3) Compute overlap height: max(0, min(ay2, by2) - max(ay1, by1)).
4) Overlap area = width × height, then apply inclusion-exclusion.
Complexity Analysis
Time: O(1).
Space: O(1).
Common Pitfalls
- Forgetting to clamp overlap width/height with max(0, ...), causing negative overlap.
- Mixing corners (left/bottom vs right/top).
- Integer overflow in fixed-width languages if constraints are expanded (use long/64-bit where needed).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int overlapW = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
int overlapH = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
int overlap = overlapW * overlapH;
return areaA + areaB - overlap;
}
}func computeArea(ax1 int, ay1 int, ax2 int, ay2 int,
bx1 int, by1 int, bx2 int, by2 int) int {
areaA := (ax2 - ax1) * (ay2 - ay1)
areaB := (bx2 - bx1) * (by2 - by1)
overlapW := max(0, min(ax2, bx2)-max(ax1, bx1))
overlapH := max(0, min(ay2, by2)-max(ay1, by1))
overlap := overlapW * overlapH
return areaA + areaB - overlap
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int overlapW = std::max(0, std::min(ax2, bx2) - std::max(ax1, bx1));
int overlapH = std::max(0, std::min(ay2, by2) - std::max(ay1, by1));
int overlap = overlapW * overlapH;
return areaA + areaB - overlap;
}
};class Solution:
def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int,
bx1: int, by1: int, bx2: int, by2: int) -> int:
area_a = (ax2 - ax1) * (ay2 - ay1)
area_b = (bx2 - bx1) * (by2 - by1)
overlap_w = max(0, min(ax2, bx2) - max(ax1, bx1))
overlap_h = max(0, min(ay2, by2) - max(ay1, by1))
overlap = overlap_w * overlap_h
return area_a + area_b - overlapvar computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
const areaA = (ax2 - ax1) * (ay2 - ay1);
const areaB = (bx2 - bx1) * (by2 - by1);
const overlapW = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
const overlapH = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
const overlap = overlapW * overlapH;
return areaA + areaB - overlap;
};中文
题目概述
给定两个与坐标轴平行的矩形 A(ax1, ay1, ax2, ay2) 和 B(bx1, by1, bx2, by2)，求它们覆盖的总面积。若有重叠区域，重叠部分只能计算一次。
核心思路
使用容斥原理：总面积 = A 面积 + B 面积 - 重叠面积。重叠面积可通过 x 轴和 y 轴投影长度相乘得到。
暴力解法与不足
按网格逐点/逐小块统计理论上可行，但坐标范围很大时完全不可行，因此必须用几何公式一次计算。
最优算法步骤
1）分别计算矩形 A 与矩形 B 的面积。
2）重叠宽度：max(0, min(ax2, bx2) - max(ax1, bx1))。
3）重叠高度：max(0, min(ay2, by2) - max(ay1, by1))。
4）重叠面积 = 宽 × 高，最后代入容斥公式。
复杂度分析
时间复杂度：O(1)。
空间复杂度：O(1)。
常见陷阱
- 忘记对重叠宽高做 max(0, ...) 截断，导致出现负面积。
- 左下角/右上角坐标混用。
- 在固定宽度整型语言中，若约束扩大可能溢出（可改用 long/64 位）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int overlapW = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
int overlapH = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
int overlap = overlapW * overlapH;
return areaA + areaB - overlap;
}
}func computeArea(ax1 int, ay1 int, ax2 int, ay2 int,
bx1 int, by1 int, bx2 int, by2 int) int {
areaA := (ax2 - ax1) * (ay2 - ay1)
areaB := (bx2 - bx1) * (by2 - by1)
overlapW := max(0, min(ax2, bx2)-max(ax1, bx1))
overlapH := max(0, min(ay2, by2)-max(ay1, by1))
overlap := overlapW * overlapH
return areaA + areaB - overlap
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
int areaA = (ax2 - ax1) * (ay2 - ay1);
int areaB = (bx2 - bx1) * (by2 - by1);
int overlapW = std::max(0, std::min(ax2, bx2) - std::max(ax1, bx1));
int overlapH = std::max(0, std::min(ay2, by2) - std::max(ay1, by1));
int overlap = overlapW * overlapH;
return areaA + areaB - overlap;
}
};class Solution:
def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int,
bx1: int, by1: int, bx2: int, by2: int) -> int:
area_a = (ax2 - ax1) * (ay2 - ay1)
area_b = (bx2 - bx1) * (by2 - by1)
overlap_w = max(0, min(ax2, bx2) - max(ax1, bx1))
overlap_h = max(0, min(ay2, by2) - max(ay1, by1))
overlap = overlap_w * overlap_h
return area_a + area_b - overlapvar computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
const areaA = (ax2 - ax1) * (ay2 - ay1);
const areaB = (bx2 - bx1) * (by2 - by1);
const overlapW = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
const overlapH = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
const overlap = overlapW * overlapH;
return areaA + areaB - overlap;
};
Comments