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:
Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.

The simple algorithm to determine whether two rectangles overlap is to exclude the situations that they do not overlap: if both rectangles are named as A and B. Then the below are four situations that A and B do not overlap.

• A is on the north of B.
• A is on the east of B.
• A is on the south of B.
• A is on the west of B.

These four situations can be checked by comparing just one coordinate either X or Y. Translating to C++ code, we have the following.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        int lowerleft0[2] = {rec1[0], rec1[1]};
        int lowerleft1[2] = {rec2[0], rec2[1]};
        int topright0[2] = {rec1[2], rec1[3]};
        int topright1[2] = {rec2[2], rec2[3]};
        
        // exclude the situations when two rectangles are not overlapping
        return (!                
           ((topright1[0] <= lowerleft0[0]) ||
           (lowerleft1[0] >= topright0[0]) ||
           (topright1[1] <= lowerleft0[1]) ||
           (lowerleft1[1] >= topright0[1])));
    }
};
</int>

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        int lowerleft0[2] = {rec1[0], rec1[1]};
        int lowerleft1[2] = {rec2[0], rec2[1]};
        int topright0[2] = {rec1[2], rec1[3]};
        int topright1[2] = {rec2[2], rec2[3]};
        
        // exclude the situations when two rectangles are not overlapping
        return (!                
           ((topright1[0] <= lowerleft0[0]) ||
           (lowerleft1[0] >= topright0[0]) ||
           (topright1[1] <= lowerleft0[1]) ||
           (lowerleft1[1] >= topright0[1])));
    }
};
</int>

See the Delphi/Pascal Implementation of this rectangle overlapping algorithm in here: Rectangle Intersection Test. The complexity is O(1) constant and so is the space complexity.

–EOF (The Ultimate Computing & Technology Blog) —