Rectangle Overlap

Easy

#0790Time: 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.2 companies

Patterns

Math Geometry

Companies

Nvidia Qualcomm

Prompt

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 == 4
rec2.length == 4
-10⁹ <= rec1[i], rec2[i] <= 10⁹
rec1 and rec2 represent 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_overlap to check for overlap on the x-axis. This is true if Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]).
Define a boolean y_overlap to check for overlap on the y-axis. This is true if Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]).
The rectangles overlap if and only if both x_overlap and y_overlap are true. Return x_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 rec1 be [x1, y1, x2, y2] and rec2 be [ax1, ay1, ax2, ay2].
The horizontal interval for rec1 is (x1, x2) and for rec2 is (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 is max(x1, ax1), and the end is min(x2, ax2). For a positive-length overlap (as required by the problem), we must have Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]).
Similarly, for the vertical intervals (y1, y2) and (ay1, ay2), we must have Math.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:

1class Solution {2    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {3        // Check if the horizontal projections overlap with positive length4        boolean x_overlap = Math.max(rec1[0], rec2[0]) < Math.min(rec1[2], rec2[2]);5        6        // Check if the vertical projections overlap with positive length7        boolean y_overlap = Math.max(rec1[1], rec2[1]) < Math.min(rec1[3], rec2[3]);8        9        return x_overlap && y_overlap;10    }11}

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 min and max functions.

An alternative, and often more intuitive, way to solve the problem is to consider the conditions under which two rectangles do not overlap. If none of these conditions are met, they must overlap.

Algorithm

Check if rec1 is entirely to the left of rec2 (rec1[2] <= rec2[0]).
Check if rec1 is entirely to the right of rec2 (rec1[0] >= rec2[2]).
Check if rec1 is entirely below rec2 (rec1[3] <= rec2[1]).
Check if rec1 is entirely above rec2 (rec1[1] >= rec2[3]).
If any of the above conditions are true, the rectangles do not overlap, so return false.
If none of the non-overlap conditions are met, the rectangles must overlap, so return true.

Walkthrough

Two rectangles fail to overlap if one is positioned entirely to the left, right, above, or below the other.

Let rec1 be [x1, y1, x2, y2] and rec2 be [ax1, ay1, ax2, ay2].
Case 1: rec1 is to the left of rec2. This occurs if the right edge of rec1 (x2) is to the left of or at the same position as the left edge of rec2 (ax1). The condition is rec1[2] <= rec2[0].
Case 2: rec1 is to the right of rec2. This occurs if the left edge of rec1 (x1) is to the right of or at the same position as the right edge of rec2 (ax2). The condition is rec1[0] >= rec2[2].
Case 3: rec1 is below rec2. This occurs if the top edge of rec1 (y2) is below or at the same position as the bottom edge of rec2 (ay1). The condition is rec1[3] <= rec2[1].
Case 4: rec1 is above rec2. This occurs if the bottom edge of rec1 (y1) is above or at the same position as the top edge of rec2 (ay2). The condition is rec1[1] >= rec2[3].

If any of these four conditions is true, the rectangles do not overlap. The function should return true (they overlap) only if the negation of the disjunction (OR) of these conditions is true.

Here is the implementation in Java:

1class Solution {2    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {3        // The rectangles do NOT overlap if one of these is true.4        // So, they DO overlap if none of these are true.5        return !(rec1[2] <= rec2[0] || // rec1 is left of rec26                 rec1[0] >= rec2[2] || // rec1 is right of rec27                 rec1[3] <= rec2[1] || // rec1 is below rec28                 rec1[1] >= rec2[3]);  // rec1 is above rec29    }10}

Complexity

Time

O(1), as the solution involves a constant number of comparisons, regardless of the input coordinate values.

Space

O(1), as no additional space is used.

Trade-offs

Pros

Optimal time and space complexity.
The logic can be considered very clear and easy to verify by enumerating all non-overlapping cases.
Can be written as a single, concise boolean expression.

Cons

There are no significant cons as this is an optimal solution.

Solutions

Solution

1class Solution {2public3  boolean isRectangleOverlap(int[] rec1, int[] rec2) {4    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];5    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];6    return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1);7  }8}

1class Solution {2public:3  bool isRectangleOverlap(vector<int> &rec1, vector<int> &rec2) {4    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];5    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];6    return !(y3 >= y2 || y4 <= y1 || x3 >= x2 || x4 <= x1);7  }8};

1class Solution:2    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool: x1, y1, x2, y2 = rec1 x3, y3, x4, y4 = rec2 return not (y3 >= y2 or y4 <= y1 or x3 >= x2 or 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.

← Previous

Previous problem

Next problem