Rectangle Overlap
EasyPrompt
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: trueExample 2:
Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: falseExample 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] <= 109rec1andrec2represent a valid rectangle with a non-zero area.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on the principle that two rectangles overlap if and only if their projections on both the X and Y axes overlap. We can check for the overlap of these one-dimensional intervals independently.
Algorithm
- Define a boolean
x_overlapto check for overlap on the x-axis. This is true ifMath.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]). - Define a boolean
y_overlapto check for overlap on the y-axis. This is true ifMath.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]). - The rectangles overlap if and only if both
x_overlapandy_overlapare true. Returnx_overlap && y_overlap.
Walkthrough
For two rectangles to have a positive area of intersection, their horizontal spans must overlap, and their vertical spans must also overlap.
- Let
rec1be[x1, y1, x2, y2]andrec2be[ax1, ay1, ax2, ay2]. - The horizontal interval for
rec1is(x1, x2)and forrec2is(ax1, ax2). These two intervals overlap if the start of the overlapping interval is less than the end of the overlapping interval. The start of the overlap ismax(x1, ax1), and the end ismin(x2, ax2). For a positive-length overlap (as required by the problem), we must haveMath.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]). - Similarly, for the vertical intervals
(y1, y2)and(ay1, ay2), we must haveMath.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]). - If both of these conditions are met, the rectangles overlap. Otherwise, they do not.
Here is the implementation in Java:
class Solution { public boolean isRectangleOverlap(int[] rec1, int[] rec2) { // Check if the horizontal projections overlap with positive length boolean x_overlap = Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]); // Check if the vertical projections overlap with positive length boolean y_overlap = Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]); return x_overlap && y_overlap; }}Complexity
Time
O(1), as the solution involves a constant number of arithmetic operations and comparisons, regardless of the input coordinate values.
Space
O(1), as no additional space is allocated that scales with the input.
Trade-offs
Pros
Optimal time and space complexity.
The logic is constructive, directly checking for the conditions of overlap.
This method can be easily adapted to calculate the area of the overlapping rectangle.
Cons
There are no significant cons as this is an optimal solution.
The logic might be slightly less direct than checking for non-overlap conditions, as it involves
minandmaxfunctions.
Solutions
Solution
class Solution {public boolean isRectangleOverlap(int[] rec1, int[] rec2) { int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3]; int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3]; return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.