What is the main idea of the 'Find the Largest Area of Square Inside Two Rectangles' problem?

The problem asks you to find the largest square area that can fit inside the intersection of at least two rectangles on a 2D plane.

How can brute force be used to solve this problem?

Brute force can be used by checking every pair of rectangles, calculating their intersection, and finding the largest square that fits in that region.

What are the potential performance issues when solving this problem?

The main performance issue arises from brute force methods that check all possible rectangle pairs, leading to a time complexity of O(n^2), which is inefficient for large inputs.

Are there optimization strategies for this problem?

Yes, you can optimize by calculating the intersection region for each pair of rectangles and only focusing on the largest square that fits inside that region.

What happens if no intersection exists between rectangles?

If no intersection exists, the result should be 0, as no square can fit inside the intersecting region.

#3047

Medium

auto_awesome数组·数学

LeetCode 题解工作台

求交集区域内的最大正方形面积

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight ，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的左下角和右上角坐标。我们定义向右的方向为 x 轴正…

数组数学几何

题目描述

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的 左下角 和 右上角 坐标。

我们定义向右的方向为 x 轴正半轴（x 坐标增加），向左的方向为 x 轴负半轴（x 坐标减少）。同样地，定义向上的方向为 y 轴正半轴（y 坐标增加），向下 的方向为 y 轴负半轴（y 坐标减少）。

你可以选择一个区域，该区域由两个矩形的交集形成。你需要找出能够放入该区域内的最大正方形面积，并选择最优解。

返回能够放入交集区域的正方形的最大可能面积，如果矩形之间不存在任何交集区域，则返回 0。

示例 1：

输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域，或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。

示例 2：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1，矩形 1 和矩形 2，或所有三个矩形的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。
请注意，区域可以由多于两个矩形的交集构成。

示例 3：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
输出：0
解释：不存在相交的矩形，因此，返回 0 。

提示：

n == bottomLeft.length == topRight.length
2 <= n <= 10³
bottomLeft[i].length == topRight[i].length == 2
1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10⁷
1 <= topRight[i][0], topRight[i][1] <= 10⁷
bottomLeft[i][0] < topRight[i][0]
bottomLeft[i][1] < topRight[i][1]

lightbulb

解题思路

方法一：枚举

我们可以枚举两个矩形，其中矩形 $1$ 的左下角和右上角坐标分别为 $(x_1, y_1)$ 和 $(x_2, y_2)$ ，矩形 $2$ 的左下角和右上角坐标分别为 $(x_3, y_3)$ 和 $(x_4, y_4)$ 。

如果矩形 $1$ 和矩形 $2$ 有交集，那么交集的坐标分别为：

左下角横坐标是两个矩形左下角横坐标的最大值，即 $\max(x_1, x_3)$ ；
左下角纵坐标是两个矩形左下角纵坐标的最大值，即 $\max(y_1, y_3)$ ；
右上角横坐标是两个矩形右上角横坐标的最小值，即 $\min(x_2, x_4)$ ；
右上角纵坐标是两个矩形右上角纵坐标的最小值，即 $\min(y_2, y_4)$ 。

那么交集的宽和高分别为 $w = \min(x_2, x_4) - \max(x_1, x_3)$ 和 $h = \min(y_2, y_4) - \max(y_1, y_3)$ 。我们取两者的最小值作为边长，即 $e = \min(w, h)$ ，如果 $e > 0$ ，那么我们就可以得到一个正方形，其面积为 $e^2$ ，我们取所有正方形的最大面积即可。

时间复杂度 $O(n^2)$ ，其中 $n$ 是矩形的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def largestSquareArea(
        self, bottomLeft: List[List[int]], topRight: List[List[int]]
    ) -> int:
        ans = 0
        for ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4)) in combinations(
            zip(bottomLeft, topRight), 2
        ):
            w = min(x2, x4) - max(x1, x3)
            h = min(y2, y4) - max(y1, y3)
            e = min(w, h)
            if e > 0:
                ans = max(ans, e * e)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands how to calculate the intersection of rectangles and how to approach the problem efficiently.
question_mark
Look for knowledge of computational geometry techniques and optimization strategies for handling large datasets.
question_mark
The candidate should identify potential trade-offs between brute force and more advanced solutions based on time and space constraints.

warning

常见陷阱

外企场景

error
Not accounting for the case where no intersection exists, which would return a result of 0.
error
Ignoring the rectangle boundaries when calculating the intersection, which may result in incorrect overlap calculations.
error
Using brute force without considering optimization, which can lead to performance issues when handling large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of calculating the largest square, the task could ask for the largest rectangle within the intersection.
arrow_right_alt
The problem could be extended to handle non-rectangular shapes in the intersection, complicating the geometric calculations.
arrow_right_alt
The problem could involve calculating the largest square inside a single rectangle, with no intersection required.

help

常见问题

外企场景

继续练习

#3027 人员站位的方案数 II #3025 人员站位的方案数 I #3102 最小化曼哈顿距离