Max Points on a Line

Problem

Given points as [x, y] pairs, return the maximum number of points that lie on one straight line.

For each anchor point, normalise the slope to every other point by dividing the coordinate differences by their greatest common divisor and counting occurrences in a hash map, with duplicate anchors handled separately. Return the best total.

Hint

Normalising the sign of dx makes opposite directions share one slope key.

Test cases

case 1

in: [[[1,1],[2,2],[3,3]]]

expected: 3

case 2

in: [[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]]

expected: 4

case 3

in: [[[1,1]]]

expected: 1

case 4

in: [[[0,0],[0,0]]]

expected: 2

case 5

in: [[[0,0],[1,1],[0,1]]]

expected: 2

Starter codePython

def max_points_on_line(points):
    # Your code here
    pass

5 test cases · run your code against them in the editor