Problem Description

The problem provides a representation of two axis-aligned rectangles. Each rectangle is described with 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. This means that the edges of the rectangle are parallel to the X and Y axes, with horizontal edges running left to right and vertical edges running bottom to top.

The task is to determine whether these two rectangles overlap with each other. Overlapping, in this context, means that the area where the two rectangles cover is more than zero. If they just touch at the edges or corners, it is not considered an overlap. The output should be true if there is an overlap, otherwise false.

Intuition

To determine if the two rectangles overlap, we look at the cases when they definitely don't overlap and invert the logic to find when they do. Rectangles do not overlap if one is completely to the left, right, above, or below the other.

• Completely to the left: This happens when the right edge of one rectangle (x2 or x4) is to the left of the left edge of the other (x1 or x3). That means x2 <= x3 or x4 <= x1.
• Completely to the right: Similarly, if the left edge of one rectangle is to the right of the right edge of the other, they don't overlap. So, x3 >= x2 or x1 >= x4.
• Completely above: If the bottom edge of one rectangle is above the top edge of the other, there's no overlap. Thus, y3 >= y2 or y1 >= y4.
• Completely below: Conversely, if the top edge of one is below the bottom edge of the other, they do not overlap. Hence, y2 <= y3 or y4 <= y1.

To resolve these conditions into a single check for non-overlapping, we can take the not of each comparison and combine them with logical or. Now, if any of these non-overlap conditions are true, we have a not operator in front which will make the whole condition false. Hence, if none of the non-overlap conditions is met, the rectangles must overlap and return not (...) will return true. The solution code effectively checks for these conditions to return the correct overlap status.

Learn more about Math patterns.

Solution Approach

The solution given follows a straightforward approach that leverages computational geometry concepts. The key idea is to determine whether two rectangles overlap without actually calculating the intersection area.

The code defines a method isRectangleOverlap which accepts two lists, rec1 and rec2, each containing the coordinates of the bottom-left and top-right corners of a rectangle. Within this method, these coordinates are unpacked into variables x1, y1, x2, y2 for rec1 and x3, y3, x4, y4 for rec2.

To determine if the rectangles overlap, the function checks the inverse of the four possible ways that the rectangles could not overlap:

1. One rectangle is to the left of the other: x3 >= x2 or x4 <= x1.
2. One rectangle is to the right of the other: x2 <= x3 or x1 >= x4.
3. One rectangle is above the other: y3 >= y2 or y1 >= y4.
4. One rectangle is below the other: y2 <= y3 or y4 <= y1.

For non-overlap, at least one of these conditions must be true. The code checks the negative condition (not) to see if none of these four non-overlapping conditions is true. If none of them holds, the rectangles must overlap, which logically means that the two rectangles do have an area of intersection.

This is accomplished in a single return statement in Python:

return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1)

This line directly translates the absence of non-overlapping conditions into a boolean result indicating whether or not the rectangles overlap.

No additional data structures or advanced algorithmic patterns are needed for this task. The solution's elegance lies in its simplicity and its O(1) time complexity, as it only involves simple arithmetic operations and logical comparisons.

Example Walkthrough

Let's consider two rectangles given by their bottom-left and top-right points:

• Rectangle 1 (rec1): [1, 1, 3, 3]
• Rectangle 2 (rec2): [2, 2, 4, 4]

We need to determine if these rectangles overlap using the approach described above. First, we unpack the coordinates:

• For rec1, we have x1 = 1, y1 = 1, x2 = 3, and y2 = 3.
• For rec2, we have x3 = 2, y3 = 2, x4 = 4, and y4 = 4.

Now, we apply the four checks to see if there is a non-overlapping condition that applies:

1. One rectangle is to the left of the other:
   This would mean that the right edge of rec1 is to the left of the left edge of rec2 (x2 <= x3), or the right edge of rec2 is to the left of the left edge of rec1 (x4 <= x1). Checking these conditions:

   • x2 <= x3 is 3 <= 2, which is false.
   • x4 <= x1 is 4 <= 1, which is false.

2. One rectangle is to the right of the other:
   This would be x3 >= x2 or x1 >= x4.
   Checking these:

   • x3 >= x2 is 2 >= 3, which is false.
   • x1 >= x4 is 1 >= 4, which is false.

3. One rectangle is above the other:
   This would be y3 >= y2 or y1 >= y4.
   Checking these:

   • y3 >= y2 is 2 >= 3, which is false.
   • y1 >= y4 is 1 >= 4, which is false.

4. One rectangle is below the other:
   This would be y2 <= y3 or y4 <= y1.
   Checking these:

   • y2 <= y3 is 3 <= 2, which is false.
   • y4 <= y1 is 4 <= 1, which is false.

Since none of these conditions are true, it means none of the non-overlapping conditions are met. Therefore, according to our function:

return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or x4 <= x1) 

The result of the function is not (false or false or false or false), which simplifies to not (false), thus returning true. Hence, using our approach, we determine that rectangle 1 and rectangle 2 do indeed overlap.

Solution Implementation

Time and Space Complexity

The given Python function isRectangleOverlap checks if two rectangles overlap. The function takes the coordinates of the bottom-left and top-right corners of each rectangle (rec1 and rec2) as inputs. The rectangles are defined by their coordinates on the x and y axes: (x1, y1) for the bottom-left corner and (x2, y2) for the top-right corner of the first rectangle, and similarly (x3, y3) and (x4, y4) for the second.

Time Complexity:

The function consists of a single return statement with a few comparisons between the input variables. Since each comparison is an O(1) operation and there are a fixed number of comparisons (specifically four), the overall time complexity of the function is O(1). This constant time complexity indicates that the function's running time does not depend on the size of the input, but rather it executes in a fixed amount of time regardless of the input.

Space Complexity:

The function does not use any additional data structures that grow with the size of the input. The space used is only for the input parameters and a fixed amount of variables for unpacking these parameters, all of which do not depend on the input size. Therefore, the space complexity of the function is also O(1). This constant space complexity denotes that the amount of memory required by the function does not change with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.