Rectangle Area
Total = sum of areas minus the overlap area; overlap dims are max(0, min - max) on each axis.
3 min read
geometry math
Problem#
Given two axis-aligned rectangles by their bottom-left and top-right corners, return their combined covered area (union).
Examples#
(-3,0,3,4),(0,-1,9,2)→45.(-2,-2,2,2),(-2,-2,2,2)→16.
Constraints#
- Coordinates fit in 32-bit signed int.
Approach#
area(A) + area(B) - area(A ∩ B). Overlap width = max(0, min(rightA, rightB) - max(leftA, leftB)), similarly for height.
Solution#
class Solution {public: int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) { long long a = (long long)(ax2 - ax1) * (ay2 - ay1); long long b = (long long)(bx2 - bx1) * (by2 - by1); long long ow = max(0, min(ax2, bx2) - max(ax1, bx1)); long long oh = max(0, min(ay2, by2) - max(ay1, by1)); return (int)(a + b - ow * oh); }};func computeArea(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 int) int { a := (ax2 - ax1) * (ay2 - ay1) b := (bx2 - bx1) * (by2 - by1) ow := min(ax2, bx2) - max(ax1, bx1) if ow < 0 { ow = 0 } oh := min(ay2, by2) - max(ay1, by1) if oh < 0 { oh = 0 } return a + b - ow*oh}
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: def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int: a = (ax2 - ax1) * (ay2 - ay1) b = (bx2 - bx1) * (by2 - by1) ow = max(0, min(ax2, bx2) - max(ax1, bx1)) oh = max(0, min(ay2, by2) - max(ay1, by1)) return a + b - ow * ohfunction computeArea(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) { const a = (ax2 - ax1) * (ay2 - ay1); const b = (bx2 - bx1) * (by2 - by1); const ow = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1)); const oh = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1)); return a + b - ow * oh;}class Solution { public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) { long a = (long) (ax2 - ax1) * (ay2 - ay1); long b = (long) (bx2 - bx1) * (by2 - by1); long ow = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1)); long oh = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1)); return (int) (a + b - ow * oh); }}function computeArea( ax1: number, ay1: number, ax2: number, ay2: number, bx1: number, by1: number, bx2: number, by2: number,): number { const a = (ax2 - ax1) * (ay2 - ay1); const b = (bx2 - bx1) * (by2 - by1); const ow = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1)); const oh = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1)); return a + b - ow * oh;}Editorial#
Inclusion-exclusion in two dimensions. The max(0, ...) guards the case where the rectangles don’t overlap (negative overlap width). long long casts prevent overflow when both areas approach (2 * 10^4)^2.
Complexity#
- Time:
O(1). - Space:
O(1).
Concept revision#
Related#