# LeetCode 836: Rectangle Overlap

## Problem Restatement

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

Each rectangle is represented as:

```python
[x1, y1, x2, y2]
```

where:

| Coordinate | Meaning |
|---|---|
| `(x1, y1)` | Bottom-left corner |
| `(x2, y2)` | Top-right corner |

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

| Item | Meaning |
|---|---|
| Input | Two rectangles `rec1` and `rec2` |
| Output | `True` if they overlap, otherwise `False` |
| Rectangle format | `[x1, y1, x2, y2]` |
| Overlap rule | Intersection area must be positive |
| Edge touching | Does not count as overlap |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
True
```

Example 2:

```python
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:

```python
False
```

Example 3:

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

The rectangles are completely separate.

So the answer is:

```python
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:

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

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

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

So the intersection width is:

```python
right - left
```

Similarly:

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

The intersection height is:

```python
top - bottom
```

The rectangles overlap exactly when both are strictly positive.

## Key Insight

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

```python
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:
   ```python id="ysluyc"
   min(rec1[2], rec2[2]) - max(rec1[0], rec2[0])
   ```

2. Compute the vertical intersection:
   ```python id="w5m0zk"
   min(rec1[3], rec2[3]) - max(rec1[1], rec2[1])
   ```

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

## Walkthrough

Use:

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

Horizontal overlap:

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

Vertical overlap:

```python
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:

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

Horizontal overlap:

```python
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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | Only a constant number of comparisons are used |
| Space | `O(1)` | No extra data structure is needed |

## Implementation

```python
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:

```python
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:

```python
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:

```python
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.

```python
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

```python
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:

| Test | Why |
|---|---|
| Normal overlap | Confirms positive-area intersection |
| Edge touching | Confirms zero width is not overlap |
| Separate rectangles | Confirms no intersection |
| Corner touching | Confirms zero-area corner contact is not overlap |
| Negative coordinates | Confirms coordinate signs do not matter |
| One rectangle inside another | Confirms containment is overlap |