algoadvance

The problem is to determine if two rectangles overlap. Each rectangle is represented by an array of four integers [x1, y1, x2, y2] where (x1, y1) represent the coordinates of its bottom-left corner, and (x2, y2) represent the coordinates of its top-right corner.

Two rectangles are considered overlapping if they share at least one common point.

Clarifying Questions

  1. Are the rectangles aligned with the coordinate axes?
    • Yes, the sides of the rectangles are parallel to the coordinate axes.
  2. Can rectangles be points or lines?
    • No, both rectangles have a positive area, meaning x1 < x2 and y1 < y2.
  3. Do we consider edges and corners touching as overlapping?
    • No, overlapping means at least one common interior point.

Strategy

To determine if two rectangles overlap, we can use the property that two rectangles do NOT overlap if one is entirely to the right, left, above, or below the other. Specifically, for two rectangles rec1 = [x1, y1, x2, y2] and rec2 = [x3, y3, x4, y4]:

If none of these conditions are true, the rectangles must overlap.

Code

Here is the implementation in Python:

def isRectangleOverlap(rec1, rec2):
    # Unpacking the coordinates for better readability
    x1, y1, x2, y2 = rec1
    x3, y3, x4, y4 = rec2
    
    # Checking if the rectangles don't overlap
    if x2 <= x3 or x4 <= x1 or y2 <= y3 or y4 <= y1:
        return False
    return True

# Example usage:
print(isRectangleOverlap([0,0,2,2], [1,1,3,3]))  # Output: True
print(isRectangleOverlap([0,0,1,1], [1,0,2,1]))  # Output: False
print(isRectangleOverlap([0,0,1,1], [2,2,3,3]))  # Output: False

Time Complexity

The time complexity of this solution is O(1) because we are performing a constant amount of operations regardless of the input size. The space complexity is also O(1) since we are only using a fixed amount of extra space.

Try our interview co-pilot at AlgoAdvance.com