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.Problem Overview: You receive the coordinates of two axis-aligned rectangles defined by their bottom-left and top-right corners. The task is to determine whether these rectangles overlap with a positive area. Touching edges or corners does not count as overlap.
Approach 1: Rectangle Non-Overlap Conditions (O(1) time, O(1) space)
The simplest way to detect overlap is to check if the rectangles are separated. Two rectangles do not overlap when one lies completely to the left, right, above, or below the other. These four cases can be expressed with coordinate comparisons: rect1.right <= rect2.left, rect1.left >= rect2.right, rect1.top <= rect2.bottom, or rect1.bottom >= rect2.top. If any condition is true, there is no overlap. Otherwise the rectangles must intersect. This method relies on simple arithmetic comparisons, runs in constant time, and is typically the cleanest implementation for problems involving geometry and coordinate ranges.
Approach 2: Checking Overlap Using Intersection (O(1) time, O(1) space)
Another way to think about the problem is to compute the potential intersection region. The width of the intersection equals min(r1.right, r2.right) - max(r1.left, r2.left), and the height equals min(r1.top, r2.top) - max(r1.bottom, r2.bottom). If both width and height are strictly greater than zero, the rectangles overlap with positive area. This approach directly models the intersection rectangle and is often easier to visualize when solving coordinate problems involving math or bounding boxes. It’s also a common pattern when extending to multiple rectangles or computing intersection area.
Recommended for interviews: The non-overlap condition approach is what interviewers usually expect. It shows you understand the geometric constraints and can convert them into concise logical checks. The intersection approach demonstrates strong spatial reasoning and becomes useful when follow-ups ask for intersection area or rectangle merging.
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.
The function checks whether any of the non-overlapping conditions are true. If none are true, it means the rectangles 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.
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])The function calculates potential overlapping parts along both axes and ensures these parts form an area (both x and y overlap must be true).
Time Complexity: O(1)
Space Complexity: O(1)
Let the coordinates of rectangle rec1 be (x_1, y_1, x_2, y_2), and the coordinates of rectangle rec2 be (x_3, y_3, x_4, y_4).
The rectangles rec1 and rec2 do not overlap if any of the following conditions are met:
y_3 geq y_2: rec2 is above rec1;y_4 leq y_1: rec2 is below rec1;x_3 geq x_2: rec2 is to the right of rec1;x_4 leq x_1: rec2 is to the left of rec1.If none of the above conditions are met, the rectangles rec1 and rec2 overlap.
The time complexity is O(1), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Rectangle Non-Overlap Conditions | Time Complexity: O(1), since the operation involves a constant number of comparisons. |
| Checking Overlap Using Intersection | Time Complexity: O(1) |
| Determine Non-Overlap Cases | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rectangle Non-Overlap Conditions | O(1) | O(1) | Best general solution. Minimal logic using four separation checks. |
| Checking Overlap Using Intersection | O(1) | O(1) | Useful when computing intersection dimensions or area. |
LeetCode 836. Rectangle Overlap Solution Explained - Java • Nick White • 20,896 views views
Watch 9 more video solutions →Practice Rectangle Overlap with our built-in code editor and test cases.
Practice on FleetCode