NeetCode #899LC-149HardMath & Geometry
← Back to All Problems#899 · #149 · Max Points on a Line(直线上最多的点数)
📌 Problem Statement & Constraints
Given an array
points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on a single straight line. Constraints: 1 <= points.length <= 300, -10^4 <= xi, yi <= 10^4, and all points are unique.💡 Core Algorithmic Approaches
- For each anchor point
i, compute the slope fromito every pointj > i. - Points lying on the same line through the anchor share the same reduced slope, so group by slope and take the largest group.
- Reduce each slope by
gcd(|dx|, |dy|)and normalise the sign so thatdx > 0, ordx == 0withdy > 0; this makes equal directions map to equal keys. - The best line through anchor
icontains1 + (largest group size)points; iterating onlyj > iavoids double counting each line.
💻 Benchmark Python3 Implementation
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
from math import gcd
from collections import defaultdict
n = len(points)
if n <= 2:
return n
best = 2
for i in range(n):
slopes = defaultdict(int)
for j in range(i + 1, n):
dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]
g = gcd(dx, dy) # gcd(0, dy) = |dy|, and never 0 here
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy # canonical direction
slopes[(dx, dy)] += 1
if slopes:
best = max(best, 1 + max(slopes.values()))
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 log V): O(n^2) slope computations, each with a gcd costing O(log V) for values up to 10^4.
💾 Space Complexity
O(n): the slope map for a single anchor.
⚠️ Interview Pitfalls & Follow-ups
- Using floating-point slopes:
dy / dxloses precision and can merge distinct directions; reduced integer pairs are exact. - Forgetting to normalise the sign:
(1, 2)and(-1, -2)describe the same line but are different tuple keys, so the group would split. - Special-casing vertical lines separately: the reduced-pair representation already encodes them as
(0, 1). - Initialising
bestto 0 or 1: any two distinct points define a line, so forn >= 2the minimum answer is 2. - Dividing by
gwhen both components are zero: points are unique, so(dx, dy)is never(0, 0); a manual gcd must still return|dy|for(0, dy).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.