Rectangle Overlap
Easy · Math · Math · Geometry
Problem
An axis-aligned rectangle is given as a list [x1, y1, x2, y2], where (x1, y1) is its bottom-left corner and (x2, y2) its top-right corner.
Two rectangles overlap when their intersection has a strictly positive area. Rectangles that only share an edge or a corner do not overlap.
Given rec1 and rec2, return true if they overlap, otherwise false.
Examples
Input: rec1 = [0,0,3,3], rec2 = [2,1,5,4] Output: true
They share the 1 × 2 region from (2, 1) to (3, 3).
Input: rec1 = [0,0,2,2], rec2 = [2,0,4,2] Output: false
They touch along the line x = 2 but share no area.
Input: rec1 = [-3,-3,-1,-1], rec2 = [1,1,2,2] Output: false
The rectangles are apart on both axes.
Constraints
- len(rec1) == len(rec2) == 4
- -10^9 <= rec1[i], rec2[i] <= 10^9
- Each rectangle has x1 < x2 and y1 < y2
Approaches
- Baseline: compute the shared width and height — time O(1), space O(1)
Follow-up
Does the same test work for boxes in three dimensions, and how many pairs overlap in a whole list of rectangles? Both are use cases below: one adds an axis, the other repeats the test for every pair.
Related problems
Start free on Cariara · Coding problems · System design studio
