Rectangle Overlap — Easy Problem & Solution

Problem statement

An axis-aligned rectangle is written as [x1, y1, x2, y2], where (x1, y1) is its bottom-left corner and (x2, y2) its top-right corner. Both given rectangles have positive area.

Two rectangles overlap when the region they share has positive area. Rectangles that only touch along an edge or at a corner do not overlap.

Return true if rec1 and rec2 overlap.

Example 1

Input: rec1 = [0,0,3,3], rec2 = [2,2,5,4]
Output: true
Explanation: They share the 1 x 1 square from (2,2) to (3,3).

Example 2

Input: rec1 = [0,0,2,2], rec2 = [2,0,4,2]
Output: false
Explanation: They meet only along the line x = 2.

Example 3

Input: rec1 = [-5,-5,5,5], rec2 = [-1,-1,1,1]
Output: true

Constraints

• rec1.length == rec2.length == 4
• -10^9 <= rec1[i], rec2[i] <= 10^9
• rec1[0] < rec1[2] and rec1[1] < rec1[3]
• rec2[0] < rec2[2] and rec2[1] < rec2[3]

How to solve Rectangle Overlap

The shared region of two axis-aligned rectangles is the product of the shared x-interval and the shared y-interval, so it has positive area exactly when both shared intervals have positive length.

Approach

1. The shared x-interval runs from max(rec1[0], rec2[0]) to min(rec1[2], rec2[2]); it has positive length when the start is strictly less than the end.
2. Do the same for the y-interval with indices 1 and 3.
3. Return true only if both are strictly positive.

Why it works

A point is in both rectangles exactly when its x-coordinate lies in both x-ranges and its y-coordinate lies in both y-ranges. The intersection of two intervals is the interval from the later start to the earlier end, so the intersection region is a rectangle whose sides are those two lengths. Its area is positive if and only if both lengths are positive — equality means the rectangles only touch.

Complexity

• Time — O(1)
• Space — O(1)

Pitfalls

• Use strict <: touching edges and corners do not count as overlap.
• Compare coordinates instead of computing width * height — with values up to 10^9 the product overflows 32-bit integers.
• Checking whether a corner of one rectangle lies inside the other misses the 'cross' arrangement where neither contains a corner of the other.

Reference solution

Python

from typing import List

def isRectangleOverlap(rec1: List[int], rec2: List[int]) -> bool:
    x_ok = max(rec1[0], rec2[0]) < min(rec1[2], rec2[2])
    y_ok = max(rec1[1], rec2[1]) < min(rec1[3], rec2[3])
    return x_ok and y_ok

JavaScript

var isRectangleOverlap = function(rec1, rec2) {
    var xOk = Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]);
    var yOk = Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]);
    return xOk && yOk;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find Nth Root of M Easy
• Valid Boomerang Easy
• Surface Area of 3D Shapes Easy
• Prime Arrangements Easy
• Day of the Week Easy
• Number of Days Between Two Dates Easy