For each point, count the maximum number of points on a straight line starting from the point, i.e., by only using the point and subsequent points. You can do it in linear time by building a hash table with the slope as the key.
Be careful with the duplicates, i.e., starting from the point p, you may see many other points with the same coordinates as p. So I use a separate variable
dupcount to keep track of it. Setting it to be
1 initially is just a simple optimization to count itself.
def maxPoints(self, points): n, np = len(points), 1 if points else 0 for i in range(n): d, dupcount = defaultdict(int), 1 for j in range(i+1, n): if points[i].x == points[j].x and points[i].y == points[j].y: dupcount += 1 else: d[sys.maxsize if points[i].x == points[j].x else float(points[i].y - points[j].y) / (points[i].x - points[j].x)] += 1 if d: np = max(np, max(d.values()) + dupcount) elif dupcount > 1: np = max(np, dupcount) return np