What is the main algorithm pattern in the Max Points on a Line problem?

The primary pattern for this problem involves array scanning combined with hash table lookup to efficiently count slopes between points.

How do you calculate the slope between two points?

The slope between two points [x1, y1] and [x2, y2] is calculated as (y2 - y1) / (x2 - x1), but you must handle vertical lines separately.

What are the edge cases to watch out for in this problem?

Be sure to handle vertical lines (undefined slope) and floating-point precision errors when calculating slopes.

What is the time complexity of the best solution for Max Points on a Line?

The best solution has a time complexity of O(n^2), where n is the number of points.

How can I improve the space complexity in this problem?

To reduce space complexity, consider using a more memory-efficient data structure for storing slopes, or explore optimization techniques.

#149

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

直线上最多的点数

给你一个数组 points ，其中 points[i] = [x i , y i ] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。示例 1：输入： points = [[1,1],[2,2],[3,3]] 输出： 3 示例 2：输入： points = [[1,1],[3,2…

数组哈希表数学几何

题目描述

给你一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

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

示例 2：

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

提示：

1 <= points.length <= 300
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
points 中的所有点 互不相同

lightbulb

解题思路

方法一：暴力枚举

我们可以枚举任意两个点 $(x_1, y_1), (x_2, y_2)$ ，把这两个点连成一条直线，那么此时这条直线上的点的个数就是 2，接下来我们再枚举其他点 $(x_3, y_3)$ ，判断它们是否在同一条直线上，如果在，那么直线上的点的个数就加 1，如果不在，那么直线上的点的个数不变。找出所有直线上的点的个数的最大值，即为答案。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(1)$ 。其中 $n$ 是数组 points 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 1
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                cnt = 2
                for k in range(j + 1, n):
                    x3, y3 = points[k]
                    a = (y2 - y1) * (x3 - x1)
                    b = (y3 - y1) * (x2 - x1)
                    cnt += a == b
                ans = max(ans, cnt)
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidate shows a clear understanding of array scanning techniques.
question_mark
Candidate can efficiently utilize hash tables for counting slopes.
question_mark
Candidate identifies edge cases, such as vertical lines, and handles them properly.

warning

常见陷阱

外企场景

error
Forgetting to handle vertical lines with an undefined slope.
error
Incorrectly handling floating-point precision when comparing slopes.
error
Not using a hash table, leading to a less efficient solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider optimizing the space complexity using different data structures for slope storage.
arrow_right_alt
Alter the problem to include collinearity checks for points in higher dimensions.
arrow_right_alt
Allow for duplicate points and adjust the solution to account for them.

help

常见问题

外企场景

继续练习

#391 完美矩形 #939 最小面积矩形 #963 最小面积矩形 II