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 LEFTis 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.