149. Max Points on a Line
Asked at LinkedIn
Difficulty
Hard
Time
O(n^2 log C)
Space
O(n)
Pattern
Array
Companies
1
Problem
You are given a list of points on a 2D plane, where each point is a pair [x, y]. All points are different from each other. Return the largest number of points that lie on one single straight line.
A line is just a straight path that goes on forever. Any two different points always sit on exactly one line. Your job is to find the line that passes through as many of the given points as possible, and report that count.
A key trap: two points can share the same slope from a fixed point and still be on the same line. So if you fix one point as an anchor, every other point is described by its slope to the anchor. Points with the same slope are on the same line through the anchor. You must compare slopes exactly — using reduced fractions, not floating-point numbers — because values like 1/3 and 0.3333333 can behave unpredictably.
Find the line with the most points
Constraints
- ●
1 <= points.length <= 300 - ●
points[i].length == 2 - ●
-10^4 <= xi, yi <= 10^4 - ●
All the points are unique.
Examples
points = [[1,1],[2,2],[3,3]]3points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]4Asked At
1 companies| 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.
Anchor each point and count slopes
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
O(n^2 log C) timefrom 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 runs in O(n^2 log C) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.