How can I determine if the points form a straight line?

You can check if the slopes between consecutive points are the same or use the cross product to avoid precision issues.

What if there are only two points?

Any two points always form a straight line, so you can immediately return true in this case.

Is it necessary to calculate the slope between every point?

You can optimize by using the cross product between points, which avoids floating-point issues and division by zero.

Can this problem be solved in less than O(n) time?

No, since you need to check all points at least once, the time complexity cannot be reduced below O(n).

How does GhostInterview help with solving math-based problems?

GhostInterview ensures you are aware of the most efficient techniques, like the cross product, and helps you avoid common mistakes in math-heavy questions.

#1232

Easy

auto_awesome数组·数学

LeetCode 题解工作台

缀点成线

给定一个整数数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x 、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。示例 1：输入： coordinates = [[1,2],[2,3],[3,4],[4…

数组数学几何

题目描述

给定一个整数数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。

示例 1：

输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：

输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10⁴ <= coordinates[i][0], coordinates[i][1] <= 10⁴
coordinates 中不含重复的点

lightbulb

解题思路

方法一：数学

时间复杂度 $O(n)$ ，其中 $n$ 表示 coordinates 数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        for x, y in coordinates[2:]:
            if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1):
                return False
        return True

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidate uses efficient math methods like slope or cross product to solve the problem.
question_mark
The solution handles edge cases, especially when there are only two points.
question_mark
Candidate explains the approach clearly, demonstrating understanding of geometry and array handling.

warning

常见陷阱

外企场景

error
Overlooking the edge case of two points, which should always return true.
error
Using division to calculate slopes, which can lead to precision issues or division by zero.
error
Failing to consider all points in the array when checking for collinearity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to check for a straight line in 3D space using an additional z-coordinate.
arrow_right_alt
Ask the candidate to find if the points form a curve or parabola instead of a straight line.
arrow_right_alt
Extend the problem to handle multiple line segments and check if they form a continuous straight line.

help

常见问题

外企场景

继续练习

#1266 访问所有点的最小时间 #1037 有效的回旋镖 #1030 距离顺序排列矩阵单元格