Max Points on a Line

Hard#149counting

You get points on a plane, no two the same. Find the largest number of them that lie on one straight line. Our example: (1, 1), (2, 3), (4, 2), (3, 5), (0, 4), (5, 9) — the answer is 4: (1, 1), (2, 3), (3, 5) and (5, 9) lie on one line.

149 Max Points on a LineWalkthrough · 1×

Example: points (1, 1), (2, 3), (4, 2), (3, 5), (0, 4), (5, 9). Each point in turn is p; the map counts the points after it by the slope of the line from p. The dashed line is the best one so far.

01234501234567891,12,34,23,50,45,9countslope: points—
point pq, or the top slopealready paired with pwas p alreadythe best line

A single point is always on a line: best = 1

01/56
restart · back · play · step
Speed
1function maxPoints(points):
2 best = 1
3 for each p in points:
4 count = empty map // slope: points
5 for each q after p in points:
6 count[slope(p, q)] += 1
7 top = largest value in count, or 0
8 best = max(best, top + 1)
9 return best
state
p
–
q
–
count
–
top
–
best
1
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Two lines through the same point p with the same slope are one line. So the points after p that share a slope with it lie on one line with p, and the map counts them.
  2. The slope is kept as a reduced fraction dy/dx, not as a division: 4/2 and 2/1 become one key, there is no rounding, and a vertical line is just 1/0.
  3. A line through an earlier point was already counted when that point was p, so each p only looks at the points after it.

Complexity

Time O(n²): every pair of points is looked at once (reducing the fraction adds a short gcd). Memory O(n): the map holds at most n − 1 slopes.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.