LeetCode Problem 836

Difficulty: 🟢 Easy
Topics: Math, Geometry

Solution

LeetCode 836, Rectangle Overlap

Problem Understanding

The problem gives us two axis-aligned rectangles, meaning their sides are parallel to the X-axis and Y-axis. Each rectangle is represented as:

[x1, y1, x2, y2]

Where:

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

The task is to determine whether these two rectangles overlap with positive area.

The phrase positive area is important. Two rectangles are considered overlapping only if the shared region has an area greater than zero. If the rectangles merely touch at an edge or corner, that does not count as overlap.

For example:

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

These rectangles share a square region from (1,1) to (2,2), which has positive area, so the answer is true.

However:

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

The rectangles touch exactly at the vertical edge x = 1. Since the overlapping region has zero width, the area is zero, so the answer is false.

The constraints tell us several useful things:

• Each rectangle always has exactly four integers.
• Coordinates can be very large, ranging from -10^9 to 10^9.
• Rectangles are guaranteed to have non-zero area, meaning x1 < x2 and y1 < y2.

Because the input size is fixed, performance is not a practical concern here. However, the problem is testing geometric reasoning and careful handling of boundary conditions.

Several edge cases can trip up a naive implementation. Rectangles that only touch at edges or corners are the most common source of mistakes. Another subtle case is when one rectangle is completely inside another. Negative coordinates also matter, but the overlap logic should work identically regardless of sign.

Approaches

Brute Force Approach

A brute force way to think about this problem is to explicitly compute the intersection rectangle and check whether its area is positive.

For two rectangles, we can determine the overlapping region:

• Left boundary: max(rec1.x1, rec2.x1)
• Right boundary: min(rec1.x2, rec2.x2)
• Bottom boundary: max(rec1.y1, rec2.y1)
• Top boundary: min(rec1.y2, rec2.y2)

Once we compute these boundaries, we calculate:

width = right - left
height = top - bottom

If both width and height are positive, then the rectangles overlap.

This approach is correct because the intersection of two axis-aligned rectangles is itself a rectangle. If either dimension is zero or negative, the overlap area is zero.

Since the input size is constant, this approach is already extremely efficient. However, we can frame an even cleaner geometric insight.

Key Insight for the Optimal Approach

Instead of directly computing the overlap area, we can think in reverse.

Two rectangles do not overlap if one of these situations occurs:

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

If none of these separation conditions hold, then the rectangles must overlap.

This observation simplifies the logic into a few comparisons.

For example:

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

We see:

rec1.x2 <= rec2.x1
1 <= 1

This means rec1 is entirely to the left of rec2, or touching the edge. Since touching does not count, we use <= instead of <.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Computes the exact overlap rectangle and checks area
Optimal	O(1)	O(1)	Uses geometric separation conditions

Algorithm Walkthrough

Optimal Algorithm

1. Extract the rectangle boundaries from rec1 and rec2.

Each rectangle gives us four values:

• Left edge: x1
• Bottom edge: y1
• Right edge: x2
• Top edge: y2

Since rectangles are axis-aligned, these values fully define the geometry. 2. Check whether one rectangle is completely to the left of the other.

This happens when:

rec1[2] <= rec2[0]

or

rec2[2] <= rec1[0]

The <= matters because touching edges does not count as overlap. 3. Check whether one rectangle is completely above or below the other.

This happens when:

rec1[3] <= rec2[1]

or

rec2[3] <= rec1[1]

4. If any separation condition is true, return false.

A separating axis means the rectangles cannot share positive area. 5. Otherwise, return true.

If there is no horizontal separation and no vertical separation, the rectangles must overlap.

Why it works

The algorithm relies on a geometric property: two axis-aligned rectangles overlap if and only if there is no separating gap between them horizontally or vertically.

If either the horizontal or vertical ranges fail to intersect with positive length, the intersection area must be zero. Conversely, if both dimensions overlap with positive length, the intersection area is positive. Since we exhaustively check all non-overlapping cases, the result is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # Check for horizontal separation
        if rec1[2] <= rec2[0] or rec2[2] <= rec1[0]:
            return False

        # Check for vertical separation
        if rec1[3] <= rec2[1] or rec2[3] <= rec1[1]:
            return False

        return True

The implementation follows the algorithm exactly.

The first if statement checks whether the rectangles are separated horizontally. If the right edge of one rectangle is less than or equal to the left edge of the other, there is no positive horizontal overlap.

The second if statement checks vertical separation using the same idea.

If neither separation exists, the rectangles overlap with positive area, so the function returns True.

The implementation avoids unnecessary calculations and directly encodes the geometric observation.

Go Solution

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
    // Check for horizontal separation
    if rec1[2] <= rec2[0] || rec2[2] <= rec1[0] {
        return false
    }

    // Check for vertical separation
    if rec1[3] <= rec2[1] || rec2[3] <= rec1[1] {
        return false
    }

    return true
}

The Go implementation mirrors the Python logic closely.

Since Go slices are used instead of Python lists, indexing syntax remains almost identical. Integer overflow is not a concern because coordinates fit safely within Go's int range on LeetCode systems. The problem guarantees valid rectangles, so we do not need extra validation for malformed input or zero-area rectangles.

Worked Examples

Example 1

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

Check	Expression	Result
Horizontal separation	2 <= 1	False
Horizontal separation	3 <= 0	False
Vertical separation	2 <= 1	False
Vertical separation	3 <= 0	False

Since no separation exists, the rectangles overlap.

Output:

true

Example 2

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

Check	Expression	Result
Horizontal separation	1 <= 1	True

Because a separation condition is met, the algorithm immediately returns false.

The rectangles touch at the edge but share no positive area.

Output:

false

Example 3

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

Check	Expression	Result
Horizontal separation	1 <= 2	True

The rectangles are completely separated horizontally, so overlap is impossible.

Output:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Performs a constant number of comparisons
Space	O(1)	Uses only a few temporary checks

The algorithm performs only four comparisons regardless of input values. Since rectangle size is fixed and no additional data structures are used, both time and space remain constant.

Test Cases

sol = Solution()

# Provided examples
assert sol.isRectangleOverlap([0, 0, 2, 2], [1, 1, 3, 3]) is True  # overlapping area
assert sol.isRectangleOverlap([0, 0, 1, 1], [1, 0, 2, 1]) is False  # touching edge
assert sol.isRectangleOverlap([0, 0, 1, 1], [2, 2, 3, 3]) is False  # fully separated

# Corner touching
assert sol.isRectangleOverlap([0, 0, 1, 1], [1, 1, 2, 2]) is False  # touching corner only

# One rectangle fully inside another
assert sol.isRectangleOverlap([0, 0, 5, 5], [1, 1, 2, 2]) is True  # contained rectangle

# Same rectangle
assert sol.isRectangleOverlap([0, 0, 2, 2], [0, 0, 2, 2]) is True  # identical rectangles

# Negative coordinates
assert sol.isRectangleOverlap([-3, -3, 1, 1], [-1, -1, 2, 2]) is True  # overlap with negatives

# No vertical overlap
assert sol.isRectangleOverlap([0, 0, 2, 2], [0, 2, 2, 4]) is False  # touching horizontally

# No horizontal overlap
assert sol.isRectangleOverlap([0, 0, 2, 2], [2, 0, 4, 2]) is False  # touching vertically

# Large coordinate values
assert sol.isRectangleOverlap(
    [-10**9, -10**9, 10**9, 10**9],
    [0, 0, 1, 1]
) is True  # extreme values

print("All tests passed!")

Test Summary

Test	Why
Standard overlap	Validates basic positive intersection
Edge touching	Ensures zero-width overlap returns false
Fully separated	Validates no overlap detection
Corner touching	Ensures zero-area corner contact returns false
Containment	Tests one rectangle inside another
Identical rectangles	Confirms full overlap works
Negative coordinates	Verifies coordinate sign does not matter
No vertical overlap	Checks vertical boundary logic
No horizontal overlap	Checks horizontal boundary logic
Large coordinates	Confirms extreme constraint handling

Edge Cases

Rectangles Touching at an Edge

A very common mistake is treating edge contact as overlap.

For example:

[0,0,1,1]
[1,0,2,1]

The rectangles meet exactly at x = 1, but the overlapping width is zero. Since the problem requires positive area, this must return false.

The implementation handles this correctly using <= rather than <.

Rectangles Touching at a Corner

Corner contact is another subtle case:

[0,0,1,1]
[1,1,2,2]

The rectangles intersect at only one point, (1,1). A point has zero area, so this is not overlap.

Because both horizontal and vertical overlap lengths are zero, the separation logic correctly returns false.

One Rectangle Completely Inside Another

Sometimes one rectangle is fully contained inside another:

[0,0,10,10]
[2,2,3,3]

A naive implementation might accidentally focus only on edge intersections and miss this case.

Our solution works because there is no horizontal or vertical separation. Since neither rectangle lies completely outside the other, the algorithm correctly returns true.