Max Points on a Line
Asked at LinkedIn
Problem
Max Points on a Line gives you a set of distinct points on a 2D plane and asks for the largest number of them that lie on a single straight line. The algorithm is simple once you anchor on each point, but representing slopes exactly — without floating-point errors — is what the interviewer is really testing.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all LinkedIn questions → |
How to Think About It
Brute force: every pair of points defines a line; for each pair, count how many other points lie on it. That is O(n³).
Key insight: fix an anchor point i. Every other point j lies on some line through i, identified by its slope. Points with the same slope from i are on the same line. Count slopes in a hash map — the biggest count plus one (the anchor) is the best line through i.
Do not store slopes as floats. 1/3 and 0.3333333 collide or split unpredictably. Instead store the reduced fraction (dy/g, dx/g) where g = gcd(dy, dx), with a normalized sign (for example, force dx > 0, or dx == 0 and dy == 1 for vertical lines).
Walkthrough for [[1,1],[2,2],[3,3]]: anchor (1,1): (2,2) gives (1,1), (3,3) gives (2,2) -> reduced (1,1). Map {(1,1): 2} -> 2 + 1 = 3.
Edge cases: one or two points (answer is n), vertical lines (dx = 0), horizontal lines (dy = 0), negative slopes. The problem guarantees distinct points, so there are no duplicates to handle.
Optimal Approach
Step 1: If n <= 2, return n.
Step 2: For each anchor i:
Create an empty map count.
For each j > i: dx = xj - xi, dy = yj - yi, g = gcd(dx, dy), reduce both by g.
Normalize the sign so that dx > 0, or if dx == 0 then dy = 1.
count[(dy, dx)] += 1, track the maximum value m.
best = max(best, m + 1).
Step 3: Return best.
Only j > i is needed because a line through i and an earlier point was already counted when that earlier point was the anchor.
Time: O(n² log C) for the gcd. Space: O(n) for the map.
What Trips People Up in Real Interviews
Using floating-point slopes. Precision errors make distinct slopes look equal (or equal slopes look different). Always mention the reduced-fraction key.
Forgetting to normalize the sign. (1, -2) and (-1, 2) describe the same slope; without normalization they land in different buckets.
Special-casing vertical lines with infinity. The gcd-reduced pair (1, 0) already represents them cleanly.
Resetting best inside the anchor loop or forgetting to add 1 for the anchor itself.
Solution Code
from math import gcd
def maxPoints(points):
n = len(points)
if n <= 2:
return n
best = 0
for i in range(n):
count = {}
x1, y1 = points[i]
for j in range(i + 1, n):
dx = points[j][0] - x1
dy = points[j][1] - y1
g = gcd(dx, dy)
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
key = (dy, dx)
count[key] = count.get(key, 0) + 1
if count:
best = max(best, max(count.values()) + 1)
return bestFrequently Asked Questions
What is the Max Points on a Line problem?
Max Points on a Line gives you a set of distinct points on a 2D plane and asks for the largest number of them that lie on a single straight line. The algorithm is simple once you anchor on each point, but representing slopes exactly — without floating-point errors — is what the interviewer is really testing.
How do you solve Max Points on a Line?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Max Points on a Line?
Max Points on a Line is asked at LinkedIn. It is a hard difficulty problem.
What are common mistakes on Max Points on a Line?
- Using floating-point slopes. Precision errors make distinct slopes look equal (or equal slopes look different). Always mention the reduced-fraction key.
- Forgetting to normalize the sign. `(1, -2)` and `(-1, 2)` describe the same slope; without normalization they land in different buckets.
- Special-casing vertical lines with infinity. The gcd-reduced pair `(1, 0)` already represents them cleanly.
- Resetting `best` inside the anchor loop or forgetting to add 1 for the anchor itself.