# Rectangle Overlap

A rectangle is represented as a list`[x1, y1, x2, y2]`, where `(x1, y1)` are the coordinates of its bottom-left corner, and`(x2, y2)` are the coordinates of its top-right corner.

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, return whether they overlap.

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

Notes:

1. Both rectangles `rec1` and `rec2` are lists of 4 integers.

2. All coordinates in rectangles will be between `-10^9` and `10^9`.

## Analysis

### Check Position

The answer for whether they don't overlap is `LEFT OR RIGHT OR UP OR DOWN`, where `OR` is the logical OR, and `LEFT`is a boolean that represents whether `rec1` is to the left of `rec2`. The answer for whether they do overlap is the negation of this.

The condition "`rec1` is to the left of `rec2`" is `rec1[2] <= rec2[0]`, that is the right-most x-coordinate of `rec1` is left of the left-most x-coordinate of `rec2`.

### Check Area

The overlapping area is positive: Thus, we can reduce the problem to the one-dimensional problem of determining whether two line segments overlap.

## Solution

### Check Position

``````class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return !(rec1[2] <= rec2[0] ||   // left
rec1[3] <= rec2[1] ||   // bottom
rec1[0] >= rec2[2] ||   // right
rec1[1] >= rec2[3]);    // top
}
}``````

### Check Area

``````class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
int x1 = 0, y1 = 1, x2 = 2, y2 = 3;
return ( Math.min(rec1[y2], rec2[y2]) - Math.max(rec1[y1], rec2[y1]) > 0 )
&& ( Math.min(rec1[x2], rec2[x2]) - Math.max(rec1[x1], rec2[x1]) > 0 );
}
}``````

Time and Space Complexity: O(1).

A rectangle with zero area inside the other rectangle would be a problem for this solution though. Need to clarify to exclude this case.

Last updated