Domain 1EasyCORE

Rectangle Overlap

The problem asks us to determine if two axis-aligned rectangles overlap. Each rectangle is defined by its bottom-left corner `(x1, y1)` and top-right corner `(x2, y2)`. The rectangles are guaranteed to be aligned with the axes.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

836. Rectangle Overlap

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 43.7%


Problem Breakdown

The problem asks us to determine if two axis-aligned rectangles overlap. Each rectangle is defined by its bottom-left corner (x1, y1) and top-right corner (x2, y2). The rectangles are guaranteed to be aligned with the axes.

Inputs:

  • Two lists rec1 and rec2, each containing four integers representing the coordinates of a rectangle.

Outputs:

  • A boolean value indicating whether the two rectangles overlap.

Implicit Constraints or Tricky Edge Cases:

  • Rectangles that touch only at the corner or edges do not count as overlapping.
  • The coordinates can be negative, and they are within the range [-10^9, 10^9].

Intuition

A brute-force approach would involve checking every point in one rectangle to see if it lies within the other rectangle. However, this is inefficient with a time complexity of O(n^2) for large rectangles.

The key insight is that two rectangles do not overlap if one is completely to the left, right, above, or below the other. Therefore, we can determine non-overlap by checking these four conditions and return false if any are met. If none of these conditions are true, the rectangles must overlap.

Approach

  1. Check Non-Overlap Conditions:

    • If one rectangle is to the left of the other: rec1[2] <= rec2[0]
    • If one rectangle is to the right of the other: rec1[0] >= rec2[2]
    • If one rectangle is above the other: rec1[3] <= rec2[1]
    • If one rectangle is below the other: rec1[1] >= rec2[3]
  2. Return Overlap Result:

    • If any of the non-overlap conditions are true, return false.
    • Otherwise, return true.

This approach ensures that we only perform a constant number of comparisons, making it very efficient.

Complexity Analysis

  • Time Complexity: O(1) because we are performing a fixed number of comparisons regardless of the size of the input.
  • Space Complexity: O(1) as no additional space is used beyond the input parameters.

Solution

def isRectangleOverlap(rec1, rec2):
    # Check if one rectangle is to the left of the other
    if rec1[2] <= rec2[0]:
        return False
    # Check if one rectangle is to the right of the other
    if rec1[0] >= rec2[2]:
        return False
    # Check if one rectangle is above the other
    if rec1[3] <= rec2[1]:
        return False
    # Check if one rectangle is below the other
    if rec1[1] >= rec2[3]:
        return False
    
    # If none of the above conditions are met, rectangles overlap
    return True

Edge Cases Handled

  • Rectangles Touching at Corners or Edges: The function correctly identifies that they do not overlap.
  • Negative Coordinates: The function handles negative coordinates as it only relies on comparisons.
  • Large Coordinate Values: Given the constraints, the function will handle large values without overflow issues since Python’s integers are arbitrary-precision.