# Rectangle Overlap
**Difficulty:** EASY
[External](https://leetcode.com/problems/rectangle-overlap)
Canonical: https://scaleengineer.com/dsa/problems/rectangle-overlap
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm)
---
## Problem
An axis-aligned rectangle is represented as a list `[x1, y1, x2, y2]`, where `(x1, y1)` is the coordinate of its bottom-left corner, and `(x2, y2)` is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is **positive**. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles `rec1` and `rec2`, return `true` _if they overlap, otherwise return_ `false`.

**Example 1:**

**Input:** rec1 = [0,0,2,2], rec2 = [1,1,3,3]
**Output:** true

**Example 2:**

**Input:** rec1 = [0,0,1,1], rec2 = [1,0,2,1]
**Output:** false

**Example 3:**

**Input:** rec1 = [0,0,1,1], rec2 = [2,2,3,3]
**Output:** false

**Constraints:**

* `rec1.length == 4`
* `rec2.length == 4`
* `-109 <= rec1[i], rec2[i] <= 109`
* `rec1` and `rec2` represent a valid rectangle with a non-zero area.

# Approaches
## Approach 1: Check for Overlap on Both Axes
This approach is based on the principle that two rectangles overlap if and only if their projections on both the X and Y axes overlap. We can check for the overlap of these one-dimensional intervals independently.
**Time:** O(1), as the solution involves a constant number of arithmetic operations and comparisons, regardless of the input coordinate values. · **Space:** O(1), as no additional space is allocated that scales with the input.
**Pros:** Optimal time and space complexity.; The logic is constructive, directly checking for the conditions of overlap.; This method can be easily adapted to calculate the area of the overlapping rectangle.
**Cons:** There are no significant cons as this is an optimal solution.; The logic might be slightly less direct than checking for non-overlap conditions, as it involves `min` and `max` functions.
### Explanation
For two rectangles to have a positive area of intersection, their horizontal spans must overlap, and their vertical spans must also overlap.

*   Let `rec1` be `[x1, y1, x2, y2]` and `rec2` be `[ax1, ay1, ax2, ay2]`.
*   The horizontal interval for `rec1` is `(x1, x2)` and for `rec2` is `(ax1, ax2)`. These two intervals overlap if the start of the overlapping interval is less than the end of the overlapping interval. The start of the overlap is `max(x1, ax1)`, and the end is `min(x2, ax2)`. For a positive-length overlap (as required by the problem), we must have `Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2])`.
*   Similarly, for the vertical intervals `(y1, y2)` and `(ay1, ay2)`, we must have `Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3])`.
*   If both of these conditions are met, the rectangles overlap. Otherwise, they do not.

Here is the implementation in Java:
```java
class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // Check if the horizontal projections overlap with positive length
        boolean x_overlap = Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]);
        
        // Check if the vertical projections overlap with positive length
        boolean y_overlap = Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]);
        
        return x_overlap && y_overlap;
    }
}
```
### Algorithm
1. Define a boolean `x_overlap` to check for overlap on the x-axis. This is true if `Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2])`.
2. Define a boolean `y_overlap` to check for overlap on the y-axis. This is true if `Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3])`.
3. The rectangles overlap if and only if both `x_overlap` and `y_overlap` are true. Return `x_overlap && y_overlap`.

## Approach 2: Check for Non-Overlap Conditions
An alternative, and often more intuitive, way to solve the problem is to consider the conditions under which two rectangles *do not* overlap. If none of these conditions are met, they must overlap.
**Time:** O(1), as the solution involves a constant number of comparisons, regardless of the input coordinate values. · **Space:** O(1), as no additional space is used.
**Pros:** Optimal time and space complexity.; The logic can be considered very clear and easy to verify by enumerating all non-overlapping cases.; Can be written as a single, concise boolean expression.
**Cons:** There are no significant cons as this is an optimal solution.
### Explanation
Two rectangles fail to overlap if one is positioned entirely to the left, right, above, or below the other.

*   Let `rec1` be `[x1, y1, x2, y2]` and `rec2` be `[ax1, ay1, ax2, ay2]`.
*   **Case 1: `rec1` is to the left of `rec2`**. This occurs if the right edge of `rec1` (`x2`) is to the left of or at the same position as the left edge of `rec2` (`ax1`). The condition is `rec1[2] <= rec2[0]`.
*   **Case 2: `rec1` is to the right of `rec2`**. This occurs if the left edge of `rec1` (`x1`) is to the right of or at the same position as the right edge of `rec2` (`ax2`). The condition is `rec1[0] >= rec2[2]`.
*   **Case 3: `rec1` is below `rec2`**. This occurs if the top edge of `rec1` (`y2`) is below or at the same position as the bottom edge of `rec2` (`ay1`). The condition is `rec1[3] <= rec2[1]`.
*   **Case 4: `rec1` is above `rec2`**. This occurs if the bottom edge of `rec1` (`y1`) is above or at the same position as the top edge of `rec2` (`ay2`). The condition is `rec1[1] >= rec2[3]`.

If any of these four conditions is true, the rectangles do not overlap. The function should return `true` (they overlap) only if the negation of the disjunction (OR) of these conditions is true.

Here is the implementation in Java:
```java
class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // The rectangles do NOT overlap if one of these is true.
        // So, they DO overlap if none of these are true.
        return !(rec1[2] <= rec2[0] || // rec1 is left of rec2
                 rec1[0] >= rec2[2] || // rec1 is right of rec2
                 rec1[3] <= rec2[1] || // rec1 is below rec2
                 rec1[1] >= rec2[3]);  // rec1 is above rec2
    }
}
```
### Algorithm
1. Check if `rec1` is entirely to the left of `rec2` (`rec1[2] <= rec2[0]`).
2. Check if `rec1` is entirely to the right of `rec2` (`rec1[0] >= rec2[2]`).
3. Check if `rec1` is entirely below `rec2` (`rec1[3] <= rec2[1]`).
4. Check if `rec1` is entirely above `rec2` (`rec1[1] >= rec2[3]`).
5. If any of the above conditions are true, the rectangles do not overlap, so return `false`.
6. If none of the non-overlap conditions are met, the rectangles must overlap, so return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
    return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isRectangleOverlap(vector<int> &rec1, vector<int> &rec2) {
    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
    return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1);
  }
};

```

### Python

```python
class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool: x1, y1, x2, y2 = rec1 x3, y3, x4, y4 = rec2 return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)

```