836. Rectangle Overlap

Problem Overview

Two axis-aligned rectangles share positive area only when their intervals overlap on both axes.

Intuition

Two axis-aligned rectangles share positive area only when their intervals overlap on both axes. Touching on an edge or corner has zero area, so the inequalities must be strict.

Algorithm

1Treat each rectangle as [x1, y1, x2, y2] bottom-left to top-right.
2Require rec1.x1 < rec2.x2 and rec2.x1 < rec1.x2 for horizontal overlap.
3Require rec1.y1 < rec2.y2 and rec2.y1 < rec1.y2 for vertical overlap.
4Return true only if both conditions hold.

Example Walkthrough

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

1.x ranges [0,2] and [1,3] overlap.
2.y ranges [0,2] and [1,3] overlap.
3.Intersection has positive area.

Output: true

Common Pitfalls

•Use strict less-than so edge-only contact returns false.
•Do not assume rec1 is left of rec2; check both orders.
•Coordinates can be negative; comparisons still work.
•The problem guarantees each input is a valid non-zero rectangle.

836.cs

// Approach: Axis-aligned rectangles overlap with positive area iff their x
// projections and y projections both strictly overlap.
// Complexity: O(1) time and O(1) extra space.
public class Solution
{
    public bool IsRectangleOverlap(int[] rec1, int[] rec2)
    {
        return rec1[0] < rec2[2] && rec2[0] < rec1[2]
            && rec1[1] < rec2[3] && rec2[1] < rec1[3];
    }
}

Was this solution helpful?