Rectangle Overlap

Difficulty: Easy | Acceptance: 46.70% | Paid: No Topics: Math, Geometry

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. Two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

• Examples
• Constraints
• Check Non-Overlap Conditions
• Check Overlap Intervals Directly

Examples

Example 1:

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

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

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

Constraints

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

Check Non-Overlap Conditions

Intuition Instead of checking if the rectangles overlap, it is simpler to check if they do not overlap. If one rectangle is to the left, right, above, or below the other, they cannot overlap.

Steps

• Check if rec1 is to the left of rec2 (rec1’s right edge is left of rec2’s left edge).
• Check if rec1 is to the right of rec2 (rec1’s left edge is right of rec2’s right edge).
• Check if rec1 is below rec2 (rec1’s top edge is below rec2’s bottom edge).
• Check if rec1 is above rec2 (rec1’s bottom edge is above rec2’s top edge).
• If any of these conditions are true, return false. Otherwise, return true.

class Solution:
    def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
        # Check if one rectangle is on left side of other
        if rec1[2] <= rec2[0] or rec2[2] <= rec1[0]:
            return False
        # Check if one rectangle is above other
        if rec1[3] <= rec2[1] or rec2[3] <= rec1[1]:
            return False
        return True

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This approach is the most efficient and easiest to implement.

Check Overlap Intervals Directly

Intuition Two rectangles overlap if their projections on the x-axis overlap and their projections on the y-axis overlap. We can calculate the length of the overlap on each axis.

Steps

• Calculate the overlap width on the x-axis: min(rec1.x2, rec2.x2) - max(rec1.x1, rec2.x1).
• Calculate the overlap height on the y-axis: min(rec1.y2, rec2.y2) - max(rec1.y1, rec2.y1).
• Return true if both width and height are positive.

class Solution:
    def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
        # Calculate overlap width
        x_overlap = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])
        # Calculate overlap height
        y_overlap = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])
        # Check if both are positive
        return x_overlap > 0 and y_overlap > 0

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This approach is mathematically equivalent to the first but explicitly computes the intersection dimensions.