⚡Flashcard Drill➔
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

  1. For each anchor point i, compute the slope from i to every point j > i.
  2. Points lying on the same line through the anchor share the same reduced slope, so group by slope and take the largest group.
  3. Reduce each slope by gcd(|dx|, |dy|) and normalise the sign so that dx > 0, or dx == 0 with dy > 0; this makes equal directions map to equal keys.
  4. The best line through anchor i contains 1 + (largest group size) points; iterating only j > i avoids 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 / dx loses 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 best to 0 or 1: any two distinct points define a line, so for n >= 2 the minimum answer is 2.
  • Dividing by g when 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems