Problem Description

The Rectangle Overlap problem asks you to determine if two axis-aligned rectangles overlap. Each rectangle is defined by a list of four integers: [x1, y1, x2, y2], where (x1, y1) represents the bottom-left corner, and (x2, y2) represents the top-right corner. The rectangles are guaranteed to be valid, meaning x1 < x2 and y1 < y2.

The task is to implement a function that takes two rectangles as input and returns True if the rectangles overlap (i.e., there is a region with positive area that is covered by both rectangles), and False otherwise. Overlap does not include touching at the edge or corner only.

Thought Process

The first idea that comes to mind is to try to check if any part of the rectangles share space. A brute-force way would be to check every possible point inside both rectangles, but this is inefficient and unnecessary. Instead, we can think about the conditions under which two rectangles do not overlap:

• If one rectangle is completely to the left of the other.
• If one rectangle is completely above the other.
• If one rectangle is completely to the right of the other.
• If one rectangle is completely below the other.

If none of these cases are true, then the rectangles must overlap. This insight shifts our approach from checking for overlap directly to checking for non-overlap, which is much simpler and faster.

Solution Approach

We use the following logic:

• Let rec1 = [x1, y1, x2, y2] and rec2 = [a1, b1, a2, b2].
• Check if one rectangle is on the left side of the other: x2 <= a1 or a2 <= x1.
• Check if one rectangle is above the other: y2 <= b1 or b2 <= y1.
• If any of these conditions is true, the rectangles do not overlap.
• Otherwise, the rectangles must overlap.

This approach is efficient because it only uses a few comparisons and avoids unnecessary computations.

Example Walkthrough

Let's consider the example:

• rec1 = [0, 0, 2, 2]
• rec2 = [1, 1, 3, 3]

Step-by-step:

1. Check if rec1 is to the left of rec2: 2 <= 1 → False
2. Check if rec2 is to the left of rec1: 3 <= 0 → False
3. Check if rec1 is above rec2: 2 <= 1 → False
4. Check if rec2 is above rec1: 3 <= 0 → False
5. None of the non-overlap conditions are true, so rectangles do overlap.

Now consider:

• rec1 = [0, 0, 1, 1]
• rec2 = [1, 1, 2, 2]

1. Check if rec1 is to the left of rec2: 1 <= 1 → True
2. Since one non-overlap condition is true, rectangles do not overlap (they only touch at the corner).

Time and Space Complexity

Brute-force approach: If we checked every point in both rectangles, the time complexity would be proportional to the area of the rectangles, which could be huge.

Optimized approach (current solution): We perform a constant number of comparisons (4 checks), so the time complexity is O(1). Space complexity is also O(1) since we use no extra data structures.

Summary

The key insight is that two rectangles do not overlap if one is completely to the left, right, above, or below the other. By checking these simple conditions, we can efficiently determine overlap in constant time. This approach avoids brute-force checking and uses only a few comparisons, making it both elegant and performant.

Code Implementation

class Solution:
    def isRectangleOverlap(self, rec1, rec2):
        # rec1: [x1, y1, x2, y2]
        # rec2: [a1, b1, a2, b2]
        return not (
            rec1[2] <= rec2[0] or  # rec1 is left of rec2
            rec2[2] <= rec1[0] or  # rec2 is left of rec1
            rec1[3] <= rec2[1] or  # rec1 is below rec2
            rec2[3] <= rec1[1]     # rec2 is below rec1
        )
      

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        return !(rec1[2] <= rec2[0] ||  // rec1 is left of rec2
                 rec2[2] <= rec1[0] ||  // rec2 is left of rec1
                 rec1[3] <= rec2[1] ||  // rec1 is below rec2
                 rec2[3] <= rec1[1]);   // rec2 is below rec1
    }
};
      

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return !(rec1[2] <= rec2[0] || // rec1 is left of rec2
                 rec2[2] <= rec1[0] || // rec2 is left of rec1
                 rec1[3] <= rec2[1] || // rec1 is below rec2
                 rec2[3] <= rec1[1]);  // rec2 is below rec1
    }
}
      

var isRectangleOverlap = function(rec1, rec2) {
    return !(
        rec1[2] <= rec2[0] || // rec1 is left of rec2
        rec2[2] <= rec1[0] || // rec2 is left of rec1
        rec1[3] <= rec2[1] || // rec1 is below rec2
        rec2[3] <= rec1[1]    // rec2 is below rec1
    );
};