836. Rectangle Overlap - Detailed Explanation

Problem Statement

You’re given two axis‑aligned rectangles on a 2D plane. Each rectangle is represented by a length‑4 array:

rec = [x1, y1, x2, y2]

where (x1, y1) is the bottom‑left corner and (x2, y2) is the top‑right corner. Return true if the two rectangles overlap (their intersection area is positive), and false otherwise. Rectangles that only touch at an edge or a corner do not count as overlapping.

Examples

Example 1

Input  
rec1 = [0,0,2,2]  
rec2 = [1,1,3,3]  
Output  true  
Explanation  
They form a 1×1 square overlap between (1,1) and (2,2).

Example 2

Input  
rec1 = [0,0,1,1]  
rec2 = [1,0,2,1]  
Output  false  
Explanation  
They touch along the vertical line x=1 but share no positive‐area region.

Example 3

Input  
rec1 = [0,0,1,1]  
rec2 = [2,2,3,3]  
Output  false  
Explanation  
They’re completely separate.

Constraints

rec1.length == rec2.length == 4
-10^9 ≤ x1 < x2 ≤ 10^9
-10^9 ≤ y1 < y2 ≤ 10^9

Hints

Under what conditions can two rectangles not overlap at all?
How can you express “rec1 is completely to the left of rec2” in terms of their coordinates?
If none of the “separated” conditions holds, can you conclude they overlap?

Approach – Constant‑Time Geometric Check

Idea

Two rectangles do not overlap if one is strictly to the left, right, above, or below the other. Concretely:

Left: rec1.x2 ≤ rec2.x1
Right: rec2.x2 ≤ rec1.x1
Below: rec1.y2 ≤ rec2.y1
Above: rec2.y2 ≤ rec1.y1

If any of these is true, there’s no positive‐area intersection. Otherwise, they must overlap.

Steps

Unpack coordinates:

x1, y1, x2, y2 = rec1  
x3, y3, x4, y4 = rec2

Check the four separation conditions.
Return ! (separated).

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time: O(1) — just a handful of comparisons.
Space: O(1) — no extra data structures.

Step‑by‑Step Walkthrough

Take rec1 = [0,0,2,2], rec2 = [1,1,3,3]:

x2=2 > x3=1 (not left)
x4=3 > x1=0 (not right)
y2=2 > y3=1 (not below)
y4=3 > y1=0 (not above)
None of the separation conditions hold → they overlap.

Take rec1 = [0,0,1,1], rec2 = [1,0,2,1]:

x2=1 ≤ x3=1 → rec1 is to the left of rec2 → no overlap.

Common Mistakes

Using < instead of ≤, which would treat edge‐touch as overlap.
Mixing up which coordinates correspond to bottom‑left vs top‑right.
Checking only horizontal or only vertical separation.

Edge Cases

Negative coordinates (the same logic applies).
Very large or very small values within 32‑bit range.
Rectangles that coincide exactly (they overlap).
One rectangle completely inside the other.

Alternative Variations

Intersection Area: compute max(0, min(x2,x4) − max(x1,x3)) × max(0, min(y2,y4) − max(y1,y3)).
Multiple Rectangles: given a list, count all overlapping pairs.
Rotated Rectangles: requires more advanced geometry (SAT, separating axis theorem).