Watch 10 video solutions for Rectangle Overlap, a easy level problem involving Math, Geometry. This walkthrough by Nick White has 20,896 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |