Rectangle Overlap
Two axis-aligned rectangles overlap iff their projections on both axes overlap (strictly, not just touch).
2 min read
geometry math
Problem#
Two axis-aligned rectangles are given as [x1, y1, x2, y2]. Return true iff their interiors overlap (touching edges/corners don’t count).
Examples#
[0,0,2,2], [1,1,3,3]→true.[0,0,1,1], [1,0,2,1]→false(only edges touch).
Constraints#
-10^9 <= xi, yi <= 10^9,x1 < x2,y1 < y2.
Approach#
Check axis-wise projection overlap. On x: max(x1a, x1b) < min(x2a, x2b); similarly on y. Both must hold.
Solution#
class Solution {public: bool isRectangleOverlap(vector<int>& a, vector<int>& b) { return max(a[0], b[0]) < min(a[2], b[2]) && max(a[1], b[1]) < min(a[3], b[3]); }};func isRectangleOverlap(a []int, b []int) bool { return max(a[0], b[0]) < min(a[2], b[2]) && max(a[1], b[1]) < min(a[3], b[3])}
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 }from typing import List
class Solution: def isRectangleOverlap(self, a: List[int], b: List[int]) -> bool: return (max(a[0], b[0]) < min(a[2], b[2]) and max(a[1], b[1]) < min(a[3], b[3]))function isRectangleOverlap(a, b) { return Math.max(a[0], b[0]) < Math.min(a[2], b[2]) && Math.max(a[1], b[1]) < Math.min(a[3], b[3]);}class Solution { public boolean isRectangleOverlap(int[] a, int[] b) { return Math.max(a[0], b[0]) < Math.min(a[2], b[2]) && Math.max(a[1], b[1]) < Math.min(a[3], b[3]); }}function isRectangleOverlap(a: number[], b: number[]): boolean { return Math.max(a[0], b[0]) < Math.min(a[2], b[2]) && Math.max(a[1], b[1]) < Math.min(a[3], b[3]);}Editorial#
Reducing 2D overlap to two independent 1D overlaps is the cleanest formulation. The strict < excludes the “share an edge but not area” case demanded by the problem.
Complexity#
- Time:
O(1). - Space:
O(1).
Concept revision#
Related#