We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rectangle Overlap

Difficulty: Easy

Problem Description

Given two axis-aligned rectangles represented as lists [x1, y1, x2, y2], where (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner, determine if the two rectangles overlap. Two rectangles overlap if the area of their intersection is positive. Rectangles that only touch at the corner or edges do not count as overlapping.

Key Insights

  • The bottom-left corner of each rectangle must be to the left and below the top-right corner of the other rectangle for them to overlap.
  • The conditions for rectangles not to overlap can be simplified to checking if one rectangle is completely to the left, right, above, or below the other rectangle.
  • The checks can be performed using the coordinates of the corners.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To determine if two rectangles overlap, we can use a straightforward approach that involves checking their coordinates. Specifically, we check if one rectangle is completely to the left, right, above, or below the other rectangle. If none of these conditions are met, the rectangles must overlap. The algorithm operates in constant time since it involves only a few comparisons.

Code Solutions

def isRectangleOverlap(rec1, rec2):
    # Check if rec1 is to the left of rec2
    if rec1[2] <= rec2[0]:
        return False
    # Check if rec1 is to the right of rec2
    if rec1[0] >= rec2[2]:
        return False
    # Check if rec1 is above rec2
    if rec1[1] >= rec2[3]:
        return False
    # Check if rec1 is below rec2
    if rec1[3] <= rec2[1]:
        return False
    # If none of the above, rectangles overlap
    return True
← Back to All Questions