LeetCode 149: Max Points on a Line (Slope Normalization + GCD Hashing)
LeetCode 149GeometryHashingInterviewToday we solve LeetCode 149 - Max Points on a Line.
Source: https://leetcode.com/problems/max-points-on-a-line/
English
Problem Summary
Given n points on a 2D plane, return the maximum number of points that lie on the same straight line.
Key Insight
For every anchor point i, compute slopes to all points j > i. Points with the same normalized slope belong to the same line through anchor i. Normalize slope as reduced integer pair (dy, dx) by GCD and sign-fix to avoid floating precision issues.
Brute Force and Limitations
Brute force checks every triple to test collinearity, which is O(n^3) and too slow near constraints. We only need pairwise slope grouping per anchor to reach O(n^2).
Optimal Algorithm Steps
1) Iterate anchor i from 0..n-1.
2) Use hashmap: key = normalized dy/dx, value = count through anchor.
3) If point j equals anchor, count as duplicate.
4) Else reduce dy, dx by gcd(|dy|, |dx|); enforce canonical sign (dx >= 0, vertical as (1,0), horizontal as (0,1)).
5) For this anchor, best line size = localMaxSlopeCount + duplicates + 1(anchor). Update global best.
Complexity Analysis
Time: O(n^2).
Space: O(n) per anchor hashmap.
Common Pitfalls
- Using floating slopes (precision collisions).
- Forgetting duplicate points.
- Not canonicalizing sign, causing same slope split into two keys.
- Missing vertical/horizontal special normalization.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2) return n;
int ans = 1;
for (int i = 0; i < n; i++) {
java.util.Map cnt = new java.util.HashMap<>();
int dup = 0, local = 0;
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if (dx == 0 && dy == 0) {
dup++;
continue;
}
int[] norm = normalize(dy, dx);
String key = norm[0] + "/" + norm[1];
int val = cnt.getOrDefault(key, 0) + 1;
cnt.put(key, val);
local = Math.max(local, val);
}
ans = Math.max(ans, local + dup + 1);
}
return ans;
}
private int[] normalize(int dy, int dx) {
if (dx == 0) return new int[]{1, 0};
if (dy == 0) return new int[]{0, 1};
if (dx < 0) { dx = -dx; dy = -dy; }
int g = gcd(Math.abs(dy), Math.abs(dx));
return new int[]{dy / g, dx / g};
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
} func maxPoints(points [][]int) int {
n := len(points)
if n <= 2 {
return n
}
ans := 1
gcd := func(a, b int) int {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}
for i := 0; i < n; i++ {
cnt := map[[2]int]int{}
dup, local := 0, 0
for j := i + 1; j < n; j++ {
dx := points[j][0] - points[i][0]
dy := points[j][1] - points[i][1]
if dx == 0 && dy == 0 {
dup++
continue
}
var key [2]int
if dx == 0 {
key = [2]int{1, 0}
} else if dy == 0 {
key = [2]int{0, 1}
} else {
if dx < 0 {
dx, dy = -dx, -dy
}
g := gcd(dx, dy)
key = [2]int{dy / g, dx / g}
}
cnt[key]++
if cnt[key] > local {
local = cnt[key]
}
}
if local+dup+1 > ans {
ans = local + dup + 1
}
}
return ans
}class Solution {
public:
int maxPoints(vector>& points) {
int n = (int)points.size();
if (n <= 2) return n;
int ans = 1;
for (int i = 0; i < n; ++i) {
unordered_map cnt;
int dup = 0, local = 0;
for (int j = i + 1; j < n; ++j) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if (dx == 0 && dy == 0) {
dup++;
continue;
}
auto [ny, nx] = normalize(dy, dx);
string key = to_string(ny) + "/" + to_string(nx);
local = max(local, ++cnt[key]);
}
ans = max(ans, local + dup + 1);
}
return ans;
}
private:
pair normalize(int dy, int dx) {
if (dx == 0) return {1, 0};
if (dy == 0) return {0, 1};
if (dx < 0) dx = -dx, dy = -dy;
int g = std::gcd(abs(dy), abs(dx));
return {dy / g, dx / g};
}
}; from collections import defaultdict
from math import gcd
from typing import List
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
if n <= 2:
return n
ans = 1
for i in range(n):
cnt = defaultdict(int)
dup = 0
local = 0
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
dx, dy = x2 - x1, y2 - y1
if dx == 0 and dy == 0:
dup += 1
continue
if dx == 0:
key = (1, 0)
elif dy == 0:
key = (0, 1)
else:
if dx < 0:
dx, dy = -dx, -dy
g = gcd(abs(dy), abs(dx))
key = (dy // g, dx // g)
cnt[key] += 1
local = max(local, cnt[key])
ans = max(ans, local + dup + 1)
return ansvar maxPoints = function(points) {
const n = points.length;
if (n <= 2) return n;
const gcd = (a, b) => {
a = Math.abs(a); b = Math.abs(b);
while (b !== 0) {
const t = a % b;
a = b;
b = t;
}
return a;
};
let ans = 1;
for (let i = 0; i < n; i++) {
const cnt = new Map();
let dup = 0, local = 0;
for (let j = i + 1; j < n; j++) {
let dx = points[j][0] - points[i][0];
let dy = points[j][1] - points[i][1];
if (dx === 0 && dy === 0) {
dup++;
continue;
}
let key;
if (dx === 0) key = '1/0';
else if (dy === 0) key = '0/1';
else {
if (dx < 0) {
dx = -dx;
dy = -dy;
}
const g = gcd(dy, dx);
key = `${dy / g}/${dx / g}`;
}
const val = (cnt.get(key) || 0) + 1;
cnt.set(key, val);
local = Math.max(local, val);
}
ans = Math.max(ans, local + dup + 1);
}
return ans;
};中文
题目概述
给定二维平面上的若干点，返回同一条直线上最多有多少个点。
核心思路
固定一个锚点 i，统计它与后续所有点的“斜率分组”。同一归一化斜率代表同一条过锚点的直线。斜率使用 (dy, dx) 的最简整数对（GCD 约分 + 符号统一），避免浮点误差。
暴力解法与不足
三重循环枚举三点共线是 O(n^3)，数据规模下不够快。更优做法是对每个锚点做一次 O(n) 哈希分组，总体 O(n^2)。
最优算法步骤
1）枚举锚点 i。
2）哈希表 key 为归一化斜率 (dy, dx)，value 为该斜率出现次数。
3）若遇到与锚点重合的点，记为重复点 dup。
4）否则对 dy, dx 做 GCD 约分并统一符号（dx >= 0；竖线固定 (1,0)，横线固定 (0,1)）。
5）该锚点下的最优值 = 该锚点最常见斜率计数 + dup + 1（锚点本身），更新全局答案。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：O(n)（每个锚点一张哈希表）。
常见陷阱
- 用浮点数表示斜率导致精度问题。
- 忘记统计与锚点重合的重复点。
- 不统一符号导致同斜率被分裂成多个 key。
- 竖线/横线未做统一归一化。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2) return n;
int ans = 1;
for (int i = 0; i < n; i++) {
java.util.Map cnt = new java.util.HashMap<>();
int dup = 0, local = 0;
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if (dx == 0 && dy == 0) {
dup++;
continue;
}
int[] norm = normalize(dy, dx);
String key = norm[0] + "/" + norm[1];
int val = cnt.getOrDefault(key, 0) + 1;
cnt.put(key, val);
local = Math.max(local, val);
}
ans = Math.max(ans, local + dup + 1);
}
return ans;
}
private int[] normalize(int dy, int dx) {
if (dx == 0) return new int[]{1, 0};
if (dy == 0) return new int[]{0, 1};
if (dx < 0) { dx = -dx; dy = -dy; }
int g = gcd(Math.abs(dy), Math.abs(dx));
return new int[]{dy / g, dx / g};
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
} func maxPoints(points [][]int) int {
n := len(points)
if n <= 2 {
return n
}
ans := 1
gcd := func(a, b int) int {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}
for i := 0; i < n; i++ {
cnt := map[[2]int]int{}
dup, local := 0, 0
for j := i + 1; j < n; j++ {
dx := points[j][0] - points[i][0]
dy := points[j][1] - points[i][1]
if dx == 0 && dy == 0 {
dup++
continue
}
var key [2]int
if dx == 0 {
key = [2]int{1, 0}
} else if dy == 0 {
key = [2]int{0, 1}
} else {
if dx < 0 {
dx, dy = -dx, -dy
}
g := gcd(dx, dy)
key = [2]int{dy / g, dx / g}
}
cnt[key]++
if cnt[key] > local {
local = cnt[key]
}
}
if local+dup+1 > ans {
ans = local + dup + 1
}
}
return ans
}class Solution {
public:
int maxPoints(vector>& points) {
int n = (int)points.size();
if (n <= 2) return n;
int ans = 1;
for (int i = 0; i < n; ++i) {
unordered_map cnt;
int dup = 0, local = 0;
for (int j = i + 1; j < n; ++j) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if (dx == 0 && dy == 0) {
dup++;
continue;
}
auto [ny, nx] = normalize(dy, dx);
string key = to_string(ny) + "/" + to_string(nx);
local = max(local, ++cnt[key]);
}
ans = max(ans, local + dup + 1);
}
return ans;
}
private:
pair normalize(int dy, int dx) {
if (dx == 0) return {1, 0};
if (dy == 0) return {0, 1};
if (dx < 0) dx = -dx, dy = -dy;
int g = std::gcd(abs(dy), abs(dx));
return {dy / g, dx / g};
}
}; from collections import defaultdict
from math import gcd
from typing import List
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
if n <= 2:
return n
ans = 1
for i in range(n):
cnt = defaultdict(int)
dup = 0
local = 0
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
dx, dy = x2 - x1, y2 - y1
if dx == 0 and dy == 0:
dup += 1
continue
if dx == 0:
key = (1, 0)
elif dy == 0:
key = (0, 1)
else:
if dx < 0:
dx, dy = -dx, -dy
g = gcd(abs(dy), abs(dx))
key = (dy // g, dx // g)
cnt[key] += 1
local = max(local, cnt[key])
ans = max(ans, local + dup + 1)
return ansvar maxPoints = function(points) {
const n = points.length;
if (n <= 2) return n;
const gcd = (a, b) => {
a = Math.abs(a); b = Math.abs(b);
while (b !== 0) {
const t = a % b;
a = b;
b = t;
}
return a;
};
let ans = 1;
for (let i = 0; i < n; i++) {
const cnt = new Map();
let dup = 0, local = 0;
for (let j = i + 1; j < n; j++) {
let dx = points[j][0] - points[i][0];
let dy = points[j][1] - points[i][1];
if (dx === 0 && dy === 0) {
dup++;
continue;
}
let key;
if (dx === 0) key = '1/0';
else if (dy === 0) key = '0/1';
else {
if (dx < 0) {
dx = -dx;
dy = -dy;
}
const g = gcd(dy, dx);
key = `${dy / g}/${dx / g}`;
}
const val = (cnt.get(key) || 0) + 1;
cnt.set(key, val);
local = Math.max(local, val);
}
ans = Math.max(ans, local + dup + 1);
}
return ans;
};
Comments