An axis-aligned rectangle is represented as 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. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.
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 rec1 and rec2, return true if they overlap, otherwise return false.
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
Example 3:
Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3] Output: false
Constraints:
rec1.length == 4rec2.length == 4-109 <= rec1[i], rec2[i] <= 109rec1 and rec2 represent a valid rectangle with a non-zero area.The key idea in Rectangle Overlap is to determine whether two axis-aligned rectangles share a region with positive area. Each rectangle is typically represented using four values: [x1, y1, x2, y2], where (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner.
Instead of computing the overlapping region directly, a simpler approach is to check when rectangles do not overlap. Two rectangles fail to overlap if one is completely to the left, right, above, or below the other. By evaluating these boundary conditions using coordinate comparisons, we can quickly determine if an overlap exists.
This method relies purely on basic geometry and coordinate comparisons, making it extremely efficient. Since only a few constant-time comparisons are required, the algorithm runs in O(1) time and uses O(1) space. This makes it ideal for interview scenarios where clarity and correctness are important.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Boundary comparison using rectangle coordinates | O(1) | O(1) |
GeeksforGeeks
This approach checks if there are conditions that confirm non-overlapping rectangles. Specifically, two rectangles do not overlap if:
If any of these conditions are true, the rectangles do not overlap. Otherwise, they do overlap.
Time Complexity: O(1), since the operation involves a constant number of comparisons.
Space Complexity: O(1), since the space used by the function is constant with respect to inputs.
1def isRectangleOverlap(rec1, rec2):
2 return not (rec1[2] <= rec2[0] or
3 rec1[0]The function checks whether any of the non-overlapping conditions are true. If none are true, it means the rectangles overlap.
This approach computes the potential intersecting rectangle and verifies if its calculated dimensions form a valid rectangle with a positive area. The logic involves:
max(rec1[0], rec2[0])min(rec1[2], rec2[2])max(rec1[1], rec2[1])min(rec1[3], rec2[3])Time Complexity: O(1)
Space Complexity: O(1)
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of rectangle and interval overlap problems appear in technical interviews, including FAANG companies. They test understanding of geometry, boundary conditions, and logical reasoning with coordinates.
No special data structure is required for this problem. Simple variables representing the rectangle coordinates are enough to compare boundaries and determine whether an overlap exists.
The optimal approach checks whether two rectangles are separated horizontally or vertically. If none of the non-overlapping conditions are true, the rectangles must overlap with positive area. This solution only requires a few coordinate comparisons and runs in constant time.
Two rectangles do not overlap if one lies completely to the left, right, above, or below the other. These conditions can be checked by comparing the x and y boundaries of the rectangles.
The function calculates potential overlapping parts along both axes and ensures these parts form an area (both x and y overlap must be true).