Problem
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
.
OR
Input - 2 Rectangles with x and y coordinates. Output - boolean value which states if they overlap or not
Examples
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
Solution
Method 1 - Analyze the overlap condition
This is a classic problem in graphics programming and game development. Let’s see how we can solve it.
Most computer screens (and now cellphone screens) have an invisible coordinate system that identifies where graphical objects are located. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. As you move down the screen, the y value increases; as you move to the right, the x value increases.
Intuition
Two rectangles can overlap if one rectangle has 0, 1, 2, or 4 corners inside the other rectangle. However, an overlapping rectangle cannot have exactly 3 corners inside the other. Another way to put it is that two rectangles overlap if part of one rectangle lies inside the other.
There are many cases where rectangles can overlap. Therefore, let’s focus on the conditions when rectangles do not intersect.
Here are examples of non-intersecting rectangles:
From those pictures, we can infer that two rectangles do not intersect if any of the following conditions are true:
- The right edge of B is to the left of the left edge of R.
- The bottom edge of B is above the top edge of R.
- The top edge of B is below the bottom edge of R.
- The left edge of B is to the right of the right edge of R.
Approach
- Extract the coordinates of the rectangles.
- Check if one rectangle is to the left of the other.
- Check if one rectangle is above the other.
- If neither condition is met, the rectangles overlap.
Code
Java
public class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
// Extract coordinates
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];
// Check if one rectangle is completely to the left or right of the other
if (x1 >= x4 || x3 >= x2) {
return false;
}
// Check if one rectangle is completely above or below the other
if (y1 >= y4 || y3 >= y2) {
return false;
}
// If neither condition is met, the rectangles overlap
return true;
}
}
Python
class Solution:
def is_rectangle_overlap(self, rec1: List[int], rec2: List[int]) -> bool:
x1, y1, x2, y2 = rec1
x3, y3, x4, y4 = rec2
# Check if one rectangle is completely to the left or right of the other
if x1 >= x4 or x3 >= x2:
return False
# Check if one rectangle is completely above or below the other
if y1 >= y4 or y3 >= y2:
return False
# If neither condition is met, the rectangles overlap
return True
Complexity
- ⏰ Time complexity:
O(1)
as the solution involves a constant number of arithmetic operations. - 🧺 Space complexity:
O(1)
as no additional space is required.