To solve the Rectangle Overlap problem, check if two rectangles share a non-zero intersection area. If their projected ranges along the x and y axes overlap, they intersect. A simple comparison of their bounds can efficiently determine overlap, which is essential for geometry-based problems.
Problem Statement
You are given two axis-aligned rectangles, each represented by a list of four integers: [x1, y1, x2, y2], where (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner of the rectangle. The edges of both rectangles are parallel to the X and Y axes. You need to determine if these two rectangles overlap in space.
The rectangles overlap if they have a positive intersection area. If they only touch at the edges or corners, they do not count as overlapping. Return true if the two rectangles overlap, otherwise return false.
Examples
Example 1
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true
Example details omitted.
Example 2
Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false
Example details omitted.
Example 3
Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]
Output: false
Example details omitted.
Constraints
- rec1.length == 4
- rec2.length == 4
- -109 <= rec1[i], rec2[i] <= 109
- rec1 and rec2 represent a valid rectangle with a non-zero area.
Solution Approach
Determine Horizontal and Vertical Overlap
To determine if two rectangles overlap, first check if they overlap along the x-axis and y-axis separately. For horizontal overlap, ensure that rec1’s right edge is beyond rec2’s left edge and rec2’s right edge is beyond rec1’s left edge. Similarly, check for vertical overlap by comparing rec1's top edge with rec2's bottom edge and vice versa.
Bounding Box Conditions
The overlap condition can be simplified to checking if one rectangle is completely to the left or right of the other, or completely above or below the other. If either of these conditions is met, the rectangles do not overlap. This simplifies the logic to comparing just the boundaries of the rectangles.
Edge Case Consideration
If the rectangles only touch at a corner or along a side, they are not considered overlapping. Ensure that the implementation handles these edge cases where the rectangles are adjacent but do not have any area in common.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | O(1) |
The time complexity for this problem is O(1) because we are only performing a constant number of comparisons to check the overlap. The space complexity is also O(1) as we are using only a fixed amount of memory for the comparison process.
What Interviewers Usually Probe
- Candidate demonstrates understanding of basic geometry principles for detecting rectangle overlap.
- Candidate avoids unnecessary complexity and sticks to simple boundary comparisons.
- Candidate effectively handles edge cases where rectangles only touch but do not overlap.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to handle cases where rectangles only touch at the corners or along edges.
- Using inefficient methods to calculate the overlap, such as iterating through points or grid-based checks.
- Confusing conditions where rectangles do not overlap due to being fully contained or adjacent without touching.
Follow-up variants
- Rectangles are rotated and no longer axis-aligned.
- Rectangles are presented as general polygons, not just rectangles.
- Multiple rectangles overlap, requiring detection of all intersections.
How GhostInterview Helps
- GhostInterview provides a step-by-step breakdown of how to check for rectangle overlap efficiently.
- GhostInterview suggests optimal comparison methods based on the problem’s constraints and failure modes.
- GhostInterview highlights common pitfalls and helps avoid them by focusing on the geometry of the problem.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What does it mean for two rectangles to overlap?
Two rectangles overlap if their intersection area is positive. This happens when their horizontal and vertical ranges on both axes intersect.
What is the time complexity of solving this problem?
The time complexity is O(1) because the solution only involves a fixed number of comparisons, regardless of the rectangle size or coordinates.
How do we handle edge cases for this problem?
Edge cases include when rectangles only touch at the corners or edges. These should be handled by checking for positive area overlap, not just touching.
Can GhostInterview help with more complex variants of this problem?
Yes, GhostInterview provides solutions and explanations for variations like rotated rectangles or cases where multiple rectangles overlap.
What mathematical concepts are involved in this problem?
This problem primarily involves basic geometry, specifically checking for intersection between axis-aligned rectangles using their coordinate ranges.
Need direct help with Rectangle Overlap instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Rectangle Overlap from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given a square room with mirrors, find which receptor a laser ray will hit first based on two integers, p and q.
Open problem page#812 Largest Triangle AreaFind the area of the largest triangle formed by three distinct points on a 2D plane.
Open problem page#883 Projection Area of 3D ShapesCalculate the projection area of a 3D shape defined by a grid of towers with varying heights.
Open problem page