What defines a boomerang in the context of this problem?

A boomerang consists of three distinct points that do not lie on a straight line, i.e., they form a triangle with a non-zero area.

Why do we calculate the area to check for collinearity?

The area of the triangle formed by the points will be zero if they are collinear. A non-zero area confirms they are not in a straight line.

What happens if two points are the same?

If any two points are identical, the points do not form a valid boomerang, as the set must consist of distinct points.

How is this problem related to geometry?

The problem involves basic geometry concepts, particularly the area of a triangle and collinearity of points in a 2D plane.

How does GhostInterview assist with problems like this?

GhostInterview helps by offering a detailed solution approach, focusing on essential steps like checking for collinearity and distinctness, which are key to solving geometric problems efficiently.

#1037

Easy

auto_awesome数组·数学

LeetCode 题解工作台

有效的回旋镖

给定一个数组 points ，其中 points[i] = [x i , y i ] 表示 X-Y 平面上的一个点，如果这些点构成一个回旋镖则返回 true 。回旋镖定义为一组三个点，这些点各不相同且不在一条直线上。示例 1：输入： points = [[1,1],[2,3],…

数组数学几何

题目描述

给定一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点，如果这些点构成一个 回旋镖 则返回 true 。

回旋镖 定义为一组三个点，这些点 各不相同 且 不在一条直线上 。

示例 1：

输入：points = [[1,1],[2,3],[3,2]]
输出：true

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：false

提示：

points.length == 3
points[i].length == 2
0 <= x_i, y_i <= 100

lightbulb

解题思路

方法一：斜率比较

设三点分别为 $(x_1,y_1)$ , $(x_2,y_2)$ , $(x_3,y_3)$ 。两点之间斜率计算公式为 $\frac{y_2-y_1}{x_2-x_1}$ 。

要使得三点不共线，需要满足 $\frac{y_2-y_1}{x_2-x_1}\neq\frac{y_3-y_2}{x_3-x_2}$ ，我们将式子变形得到 $(y_2-y_1)*(x_3-x_2) \neq (y_3-y_2)*(x_2-x_1)$ 。

注意：

当两点之间斜率不存在，即 $x_1=x_2$ ，上述变式仍然成立；
若斜率除法运算比较存在精度问题，同样可以变换为乘法。

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

1

2

3

4

5

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        (x1, y1), (x2, y2), (x3, y3) = points
        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient use of mathematical properties to solve the problem.
question_mark
Expect the candidate to explain collinearity and how the area of a triangle can help determine this.
question_mark
Candidates should confirm that all points are distinct before proceeding with further checks.

warning

常见陷阱

外企场景

error
Confusing collinearity check with simple distance calculations, which do not guarantee non-collinearity.
error
Overlooking the distinctness of the points, leading to incorrect conclusions about the boomerang formation.
error
Not understanding how the area formula directly applies to this problem for determining valid boomerangs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling higher dimensions if the problem was extended to more than 2D.
arrow_right_alt
Checking for a set of points beyond three, such as determining if any subset forms a boomerang.
arrow_right_alt
Adapting the solution for larger inputs or multiple sets of points.

help

常见问题

外企场景

继续练习

#1030 距离顺序排列矩阵单元格 #973 最接近原点的 K 个点 #963 最小面积矩形 II