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.

#836

Easy

auto_awesome数学·结合·几何

LeetCode 题解工作台

矩形重叠

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标， (x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。给出两个矩形 rec1…

数学几何

题目描述

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：

输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：

输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

示例 3：

输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输出：false

提示：

rect1.length == 4
rect2.length == 4
-10⁹ <= rec1[i], rec2[i] <= 10⁹
rec1 和 rec2 表示一个面积不为零的有效矩形

lightbulb

解题思路

方法一：判断不重叠的情况

我们记矩形 $\text{rec1}$ 的坐标点为 $(x_1, y_1, x_2, y_2)$ ，矩形 $\text{rec2}$ 的坐标点为 $(x_3, y_3, x_4, y_4)$ 。

那么当满足以下任一条件时，矩形 $\text{rec1}$ 和 $\text{rec2}$ 不重叠：

满足 $y_3 \geq y_2$ ，即 $\text{rec2}$ 在 $\text{rec1}$ 的上方；
满足 $y_4 \leq y_1$ ，即 $\text{rec2}$ 在 $\text{rec1}$ 的下方；
满足 $x_3 \geq x_2$ ，即 $\text{rec2}$ 在 $\text{rec1}$ 的右方；
满足 $x_4 \leq x_1$ ，即 $\text{rec2}$ 在 $\text{rec1}$ 的左方。

当以上条件都不满足时，矩形 $\text{rec1}$ 和 $\text{rec2}$ 重叠。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of basic geometry principles for detecting rectangle overlap.
question_mark
Candidate avoids unnecessary complexity and sticks to simple boundary comparisons.
question_mark
Candidate effectively handles edge cases where rectangles only touch but do not overlap.

warning

常见陷阱

外企场景

error
Forgetting to handle cases where rectangles only touch at the corners or along edges.
error
Using inefficient methods to calculate the overlap, such as iterating through points or grid-based checks.
error
Confusing conditions where rectangles do not overlap due to being fully contained or adjacent without touching.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Rectangles are rotated and no longer axis-aligned.
arrow_right_alt
Rectangles are presented as general polygons, not just rectangles.
arrow_right_alt
Multiple rectangles overlap, requiring detection of all intersections.

help

常见问题

外企场景

继续练习

#858 镜面反射 #812 最大三角形面积 #883 三维形体投影面积