An easy(I hope) to read 79 ms Python solution


  • 0
    S
    class Solution(object):
        def maxPoints(self, points):
    
            # Handle empty input
            if not points:
                return 0
    
            # Handle input of a single point or multiple identical points
            if len(set([(point.x, point.y) for point in points])) == 1:
                return len(points)
            
            slopes = []
            for i in xrange(len(points)):
                # Take a pair of points from the list
                if i + 1 == len(points):
                    first, second = points[i - 1], points[i]
                else:
                    first, second = points[i], points[i + 1]
                    
                if first.x == second.x and first.y == second.y:
                    continue
                
                # Skip current two points
                rest = points[:]
                rest.remove(first)
                rest.remove(second)
                
                # Any two points are on the slope
                slope = 2
    
                # Take each remaining point and determine weather it's on the same slope as the first two
                for point in rest:
                    if self.onSlope(first, second, point):
                        slope += 1
    
                slopes.append(slope)
    
            return max(slopes)
                
        def onSlope(self, p1, p2, p3):
            return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) == 0
    

Log in to reply
 

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