# Python O(n^3) time/ O(n) space solution

• I know there are better solutions. This seems very easy/readable and a little bit different, though.

Basically: Draw a line between two distinct points and then look for other distinct colinear points. If a,b,c and a,b,d are colinear this means all of them are on the same line.

``````def is_collinear(p1, p2, p3):
return (p2.y - p1.y) * (p3.x - p2.x) == (p3.y - p2.y) * (p2.x - p1.x)

class MyPoint(object):
def __init__(self, x, y):
self.x = x
self.y = y

def __hash__(self):
return hash((self.x, self.y))

def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)

def __repr__(self):
return "%s:%s" % (self.x, self.y,)

from collections import defaultdict

class Solution(object):
def maxPoints(self, points):
W = defaultdict(int)
r = 0
for p in points:
mp = MyPoint(p.x, p.y)
W[mp] += 1
r = max(r, W[mp])

P = list(W.keys())
N = len(P)
for i in range(N):
for j in range(i+1, N):
npc = W[P[i]] + W[P[j]]
for k in range(j+1, N):
if is_collinear(P[i], P[j], P[k]):
npc += W[P[k]]
r = max(r, npc)
return r
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.