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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rectangle Overlap

Number: 866

Difficulty: Easy

Paid? No

Companies: Amazon, Microsoft, Qualcomm, Meta, Oracle

Problem Description

Given two axis-aligned rectangles rec1 and rec2, where each is represented as a list [x1, y1, x2, y2] (with (x1, y1) representing the bottom-left corner and (x2, y2) representing the top-right corner), determine if the two rectangles overlap. Two rectangles overlap if and only if the area of their intersection is positive (i.e., they are not merely touching at the edges or corners).

Key Insights

  • Two rectangles do not overlap if one is completely to the left or to the right of the other.
  • Two rectangles do not overlap if one is completely above or below the other.
  • By checking the non-overlapping conditions and taking the negation, you can determine if there is an overlap.

Space and Time Complexity

Time Complexity: O(1) – Only constant time checks are performed. Space Complexity: O(1) – Only a fixed amount of extra space is used.

Solution

The solution checks if one rectangle is entirely to the left of the other by comparing the x-coordinates, and similarly if one is entirely above or below the other by comparing the y-coordinates. If any of these non-overlapping conditions are true, the rectangles do not overlap and the answer is false. Otherwise, they overlap and the answer is true.

Data structures used: Basic integer comparisons. Algorithmic approach: Conditional checks based on the positional relationships of the rectangles.

Code Solutions

# Python solution for determining rectangle overlap

def is_rectangle_overlap(rec1, rec2):
    # rec1: [x1, y1, x2, y2], rec2: [x1, y1, x2, y2]
    
    # Check if one rectangle is to the left of the other:
    if rec1[2] <= rec2[0]:
        # rec1 is to the left of rec2
        return False
    if rec2[2] <= rec1[0]:
        # rec2 is to the left of rec1
        return False

    # Check if one rectangle is above the other:
    if rec1[3] <= rec2[1]:
        # rec1 is below rec2
        return False
    if rec2[3] <= rec1[1]:
        # rec2 is below rec1
        return False

    # Rectangles overlap with positive area
    return True

# Example usage:
print(is_rectangle_overlap([0,0,2,2], [1,1,3,3]))  # Output: True
← Back to All Questions