LeetCode 836: Rectangle Overlap

Problem Restatement

We are given two axis-aligned rectangles, rec1 and rec2.

Each rectangle is represented as:

[x1, y1, x2, y2]

where:

We need to return True if the two rectangles overlap.

Overlap means their intersection has positive area. If two rectangles only touch at an edge or corner, they do not overlap.

Input and Output

Function shape:

class Solution:
    def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
        ...

Examples

Example 1:

rec1 = [0, 0, 2, 2]
rec2 = [1, 1, 3, 3]

The rectangles overlap in the square from (1, 1) to (2, 2).

The overlap has positive width and positive height.

So the answer is:

True

Example 2:

rec1 = [0, 0, 1, 1]
rec2 = [1, 0, 2, 1]

The rectangles touch at the vertical edge x = 1.

The intersection has zero width.

So the answer is:

False

Example 3:

rec1 = [0, 0, 1, 1]
rec2 = [2, 2, 3, 3]

The rectangles are completely separate.

So the answer is:

False

First Thought: Compute the Intersection

Two rectangles overlap if their intersection rectangle has positive width and positive height.

The intersection’s left edge is the larger of the two left edges:

left = max(rec1[0], rec2[0])

The intersection’s right edge is the smaller of the two right edges:

right = min(rec1[2], rec2[2])

So the intersection width is:

right - left

Similarly:

bottom = max(rec1[1], rec2[1])
top = min(rec1[3], rec2[3])

The intersection height is:

top - bottom

The rectangles overlap exactly when both are strictly positive.

Key Insight

Because touching edges do not count, we must use strict comparison:

width > 0 and height > 0

If width is 0, they only touch vertically.

If height is 0, they only touch horizontally.

Either case gives zero area, so it is not overlap.

Algorithm

1. Compute the horizontal intersection:

   min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])

2. Compute the vertical intersection:

   min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])

3. Return True only if both values are greater than 0.

Walkthrough

Use:

rec1 = [0, 0, 2, 2]
rec2 = [1, 1, 3, 3]

Horizontal overlap:

left = max(0, 1) = 1
right = min(2, 3) = 2
width = 2 - 1 = 1

Vertical overlap:

bottom = max(0, 1) = 1
top = min(2, 3) = 2
height = 2 - 1 = 1

Both width and height are positive.

So the rectangles overlap.

Now use:

rec1 = [0, 0, 1, 1]
rec2 = [1, 0, 2, 1]

Horizontal overlap:

left = max(0, 1) = 1
right = min(1, 2) = 1
width = 1 - 1 = 0

The width is zero, so the rectangles only touch at an edge.

They do not overlap.

Correctness

For two axis-aligned rectangles to have positive-area intersection, their projections must overlap on both axes.

On the x-axis, the shared interval starts at the larger left edge and ends at the smaller right edge. Its length is:

min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])

This length is positive exactly when the rectangles share horizontal space with nonzero width.

On the y-axis, the shared interval starts at the larger bottom edge and ends at the smaller top edge. Its length is:

min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])

This length is positive exactly when the rectangles share vertical space with nonzero height.

The intersection area is positive exactly when both the shared width and shared height are positive.

The algorithm checks exactly these two conditions, so it returns True exactly when the rectangles overlap.

Complexity

Implementation

class Solution:
    def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
        width = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])
        height = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])

        return width > 0 and height > 0

Code Explanation

The horizontal overlap width is:

width = min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])

rec1[2] and rec2[2] are right edges.

rec1[0] and rec2[0] are left edges.

The vertical overlap height is:

height = min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])

rec1[3] and rec2[3] are top edges.

rec1[1] and rec2[1] are bottom edges.

Finally:

return width > 0 and height > 0

requires positive area.

Using >= 0 would be wrong because rectangles that only touch at an edge or corner do not count as overlapping.

Alternative Implementation

We can also check the four ways rectangles fail to overlap.

Two rectangles do not overlap if one is completely left, right, below, or above the other.

class Solution:
    def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
        return not (
            rec1[2] <= rec2[0] or
            rec2[2] <= rec1[0] or
            rec1[3] <= rec2[1] or
            rec2[3] <= rec1[1]
        )

This is also O(1).

The <= comparisons are important because edge-touching is not overlap.

Testing

def run_tests():
    s = Solution()

    assert s.isRectangleOverlap([0, 0, 2, 2], [1, 1, 3, 3]) is True
    assert s.isRectangleOverlap([0, 0, 1, 1], [1, 0, 2, 1]) is False
    assert s.isRectangleOverlap([0, 0, 1, 1], [2, 2, 3, 3]) is False
    assert s.isRectangleOverlap([0, 0, 2, 2], [2, 2, 3, 3]) is False
    assert s.isRectangleOverlap([-2, -2, 2, 2], [-1, -1, 1, 1]) is True
    assert s.isRectangleOverlap([0, 0, 3, 3], [1, 1, 2, 2]) is True

    print("all tests passed")

run_tests()

Test meaning: