305. Rectangle Overlap

Two axis-aligned rectangles overlap with positive area exactly when their shadows overlap on BOTH the x-axis and the y-axis at the same time.

Key idea

A 2-D overlap question collapses into two independent 1-D questions. Project each rectangle onto the x-axis and onto the y-axis. The rectangles overlap with positive area if and only if their x-projections overlap and their y-projections overlap.

Two intervals [a1, a2] and [b1, b2] overlap with positive length when a1 < b2 and b1 < a2. Note the strict <: if they only touch (a2 == b1) the shared length is zero, which the problem tells us does not count as overlap.

With rec = [x1, y1, x2, y2]:

• x-projection of a rectangle is [x1, x2] → indices [0, 2]
• y-projection is [y1, y2] → indices [1, 3]

So the whole answer is a single boolean:

rec1[0] < rec2[2] and rec2[0] < rec1[2]   # x-projections overlap
and rec1[1] < rec2[3] and rec2[1] < rec1[3]   # y-projections overlap

Walk-through: rec1 = [0,0,2,2], rec2 = [1,1,3,3]

1. X-axis. rec1 spans x in [0, 2], rec2 spans x in [1, 3]. Check rec1[0] < rec2[2] → 0 < 3 ✓ and rec2[0] < rec1[2] → 1 < 2 ✓. The x-shadows overlap over [1, 2] — positive width.
2. Y-axis. rec1 spans y in [0, 2], rec2 spans y in [1, 3]. Check rec1[1] < rec2[3] → 0 < 3 ✓ and rec2[1] < rec1[3] → 1 < 2 ✓. The y-shadows overlap over [1, 2] — positive height.
3. Both axes overlap, so the rectangles share the region x in [1,2], y in [1,2], which has positive area → true.

Why touching does not count

For rec1 = [0,0,1,1], rec2 = [1,0,2,1] the x-check rec2[0] < rec1[2] is 1 < 1, which is false. The rectangles meet along the vertical line x = 1 but the intersection is a segment of zero area, so the strict comparison correctly returns false.

Complexity

• Time: O(1) — four comparisons regardless of coordinate size.
• Space: O(1) — no extra storage.

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // Overlap with positive area iff the x-projections overlap AND the
        // y-projections overlap. Strict "<" makes touching edges/corners
        // (zero-area contact) count as no overlap.
        return rec1[0] < rec2[2]
            && rec2[0] < rec1[2]
            && rec1[1] < rec2[3]
            && rec2[1] < rec1[3];
    }
}