Problem Description

You are given two axis-aligned rectangles represented as lists. Each rectangle is defined by four coordinates [x1, y1, x2, y2], where:

• (x1, y1) is the bottom-left corner
• (x2, y2) is the top-right corner

The rectangles are axis-aligned, meaning:

• Top and bottom edges are parallel to the X-axis
• Left and right edges are parallel to the Y-axis

Your task is to determine if the two rectangles overlap. Two rectangles overlap when they share a common area (the intersection area is positive). Note that rectangles that only touch at corners or edges do NOT count as overlapping.

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

The solution works by checking for non-overlapping conditions. Two rectangles do not overlap if:

• Rectangle 2 is completely above rectangle 1: y3 >= y2
• Rectangle 2 is completely below rectangle 1: y4 <= y1
• Rectangle 2 is completely to the right of rectangle 1: x3 >= x2
• Rectangle 2 is completely to the left of rectangle 1: x4 <= x1

If none of these conditions are true, the rectangles must overlap. The code returns the negation of these conditions combined with OR operators: not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1).

Intuition

When thinking about whether two rectangles overlap, it's often easier to think about when they DON'T overlap. This is a common problem-solving technique - sometimes the complement of what we want is simpler to express.

Consider all the ways two rectangles can be positioned without overlapping:

1. One rectangle can be completely to the left of the other
2. One rectangle can be completely to the right of the other
3. One rectangle can be completely above the other
4. One rectangle can be completely below the other

If we can identify these non-overlapping cases, then any situation that doesn't fall into these categories must be an overlapping case.

Let's think about each non-overlapping scenario:

• Rectangle 2 is to the right of rectangle 1: This happens when the left edge of rectangle 2 (x3) is at or beyond the right edge of rectangle 1 (x2), giving us x3 >= x2
• Rectangle 2 is to the left of rectangle 1: This happens when the right edge of rectangle 2 (x4) is at or to the left of the left edge of rectangle 1 (x1), giving us x4 <= x1
• Rectangle 2 is above rectangle 1: This happens when the bottom edge of rectangle 2 (y3) is at or above the top edge of rectangle 1 (y2), giving us y3 >= y2
• Rectangle 2 is below rectangle 1: This happens when the top edge of rectangle 2 (y4) is at or below the bottom edge of rectangle 1 (y1), giving us y4 <= y1

If ANY of these conditions is true, the rectangles don't overlap. Therefore, rectangles overlap when NONE of these conditions are true, which we can express as: not (condition1 or condition2 or condition3 or condition4).

This negative logic approach is elegant because it reduces a potentially complex overlap calculation to just checking four simple boundary conditions.

Learn more about Math patterns.

Solution Approach

The implementation follows the non-overlap detection strategy identified in our intuition. We check for all cases where the rectangles don't overlap and negate the result.

First, we extract the coordinates from both rectangles:

• Rectangle 1: (x1, y1, x2, y2) where (x1, y1) is bottom-left and (x2, y2) is top-right
• Rectangle 2: (x3, y3, x4, y4) where (x3, y3) is bottom-left and (x4, y4) is top-right

Next, we identify the four non-overlapping conditions:

1. Rectangle 2 is above Rectangle 1: y3 >= y2
   • The bottom of rec2 is at or above the top of rec1
2. Rectangle 2 is below Rectangle 1: y4 <= y1
   • The top of rec2 is at or below the bottom of rec1
3. Rectangle 2 is to the right of Rectangle 1: x3 >= x2
   • The left edge of rec2 is at or beyond the right edge of rec1
4. Rectangle 2 is to the left of Rectangle 1: x4 <= x1
   • The right edge of rec2 is at or to the left of the left edge of rec1

The key insight is that if ANY of these conditions is true, the rectangles don't overlap. We combine these conditions with the logical OR operator: (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1).

Finally, since we want to return true when rectangles DO overlap, we negate the entire expression:

return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)

This approach is efficient with O(1) time complexity and O(1) space complexity, as we only perform four comparisons without using any additional data structures.

Example Walkthrough

Let's walk through the solution with two concrete examples to see how the non-overlapping conditions work.

Example 1: Overlapping Rectangles

• Rectangle 1: [0, 0, 2, 2] - a square from (0,0) to (2,2)
• Rectangle 2: [1, 1, 3, 3] - a square from (1,1) to (3,3)

Let's extract the coordinates:

• rec1: x1=0, y1=0, x2=2, y2=2
• rec2: x3=1, y3=1, x4=3, y4=3

Now check each non-overlapping condition:

1. Is rec2 above rec1? y3 >= y2 → 1 >= 2 → False
2. Is rec2 below rec1? y4 <= y1 → 3 <= 0 → False
3. Is rec2 to the right of rec1? x3 >= x2 → 1 >= 2 → False
4. Is rec2 to the left of rec1? x4 <= x1 → 3 <= 0 → False

Since all conditions are false: not (False or False or False or False) = not False = True

The rectangles overlap! They share the area from (1,1) to (2,2).

Example 2: Non-Overlapping Rectangles

• Rectangle 1: [0, 0, 2, 2] - a square from (0,0) to (2,2)
• Rectangle 2: [3, 0, 5, 2] - a rectangle from (3,0) to (5,2)

Let's extract the coordinates:

• rec1: x1=0, y1=0, x2=2, y2=2
• rec2: x3=3, y3=0, x4=5, y4=2

Check each non-overlapping condition:

1. Is rec2 above rec1? y3 >= y2 → 0 >= 2 → False
2. Is rec2 below rec1? y4 <= y1 → 2 <= 0 → False
3. Is rec2 to the right of rec1? x3 >= x2 → 3 >= 2 → True ✓
4. Is rec2 to the left of rec1? x4 <= x1 → 5 <= 0 → False

Since at least one condition is true: not (False or False or True or False) = not True = False

The rectangles don't overlap! Rectangle 2 is completely to the right of rectangle 1 (there's a gap between x=2 and x=3).

This demonstrates how the algorithm correctly identifies both overlapping and non-overlapping cases by checking for separation conditions.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the algorithm performs a fixed number of operations regardless of input size. It extracts 8 coordinate values from the two input lists and performs exactly 4 comparison operations (y3 >= y2, y4 <= y1, x3 >= x2, x4 <= x1) along with logical operations. Since all these operations take constant time, the overall time complexity is constant.

The space complexity is O(1) because the algorithm only uses a fixed amount of extra space. It creates 8 variables (x1, y1, x2, y2, x3, y3, x4, y4) to store the coordinate values extracted from the input lists. The number of variables used does not depend on the input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Edge-Touching with Overlapping

The Pitfall: A common mistake is misunderstanding the problem statement regarding edge-touching rectangles. The problem explicitly states that rectangles that only touch at corners or edges do NOT count as overlapping. However, developers might incorrectly use > and < operators instead of >= and <=, which would treat edge-touching rectangles as overlapping.

Incorrect Implementation:

# WRONG: This would consider edge-touching rectangles as overlapping
return not (y3 > y2 or y4 < y1 or x3 > x2 or x4 < x1)

Why This Fails:

• When rec1 = [0, 0, 2, 2] and rec2 = [2, 0, 4, 2] (rectangles share a vertical edge)
• Using x3 > x2 would evaluate to 2 > 2 = False
• This would incorrectly return True (overlapping) when they should return False

Correct Solution: Use >= and <= operators to properly exclude edge-touching cases:

return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)

2. Incorrect Coordinate Assignment

The Pitfall: Assuming the wrong coordinate system or mixing up which corner is which. The problem states that (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner, but developers might accidentally treat them differently.

Common Mistakes:

• Treating (x1, y1) as top-left instead of bottom-left
• Assuming y1 > y2 (inverted y-axis) when actually y2 > y1
• Mixing up the coordinate indices when extracting from the list

Prevention: Always verify:

• x1 < x2 (left edge is less than right edge)
• y1 < y2 (bottom edge is less than top edge)

3. Attempting to Calculate Intersection Area

The Pitfall: Over-engineering the solution by trying to calculate the actual intersection area when the problem only asks for a boolean result.

Inefficient Approach:

# Unnecessary complexity
intersection_width = min(x2, x4) - max(x1, x3)
intersection_height = min(y2, y4) - max(y1, y3)
return intersection_width > 0 and intersection_height > 0

Why The Simple Solution is Better:

• The non-overlap check is more intuitive and less error-prone
• It avoids potential issues with floating-point arithmetic
• It's more efficient with fewer operations

4. Forgetting to Negate the Result

The Pitfall: Since we're checking for non-overlapping conditions, forgetting the not operator will return the opposite of what's expected.

Wrong:

# Returns True when rectangles DON'T overlap (opposite of desired behavior)
return (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)

Correct:

return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)

Debugging Tip: Test with simple cases like [0,0,1,1] and [0,0,1,1] (identical rectangles) which should definitely return True for overlap.