Leetcode 149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/

The basic thought is to count the points that have the same slope to every point. Also do not miss the vertical lines.

Solution:

# T:O(n^2) S:O(n)
class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        max_points = 0
        for i, start in enumerate(points):
            slope_count, same = {}, 1
            for j in xrange(i + 1, len(points)):
                end = points[j]
                if start.x == end.x and start.y == end.y:
                    same += 1
                else:
                    slope = float("inf")
                    if start.x - end.x != 0:
                        slope = (start.y - end.y) * 1.0 / (start.x - end.x)
                    if slope not in slope_count:
                        slope_count[slope] = 1
                    else:
                        slope_count[slope] += 1
            
            current_max = same            
            for slope in slope_count:
                current_max = max(current_max, slope_count[slope] + same)
                
            max_points = max(max_points, current_max)
            
        return max_points

Run Time: 80 ms