#836

Easy

LeetCode Problem Workspace

Rectangle Overlap

Determine if two axis-aligned rectangles overlap based on their coordinates.

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.

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.

terminal

Solution

Solution 1: Determine Non-Overlap Cases

Let the coordinates of rectangle $\text{rec1}$ be $(x_1, y_1, x_2, y_2)$, and the coordinates of rectangle $\text{rec2}$ be $(x_3, y_3, x_4, y_4)$.

1

2

3

4

5

class Solution:
    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)

Continue Practicing

#858 mirror reflection #812 largest triangle area #883 projection area of 3d shapes