Max Points on a Line

Problems: Max Points on a Line

An interesting truth about leetcode: Hard problems don't require brilliant ideas but ability to lead through complicate method. To solve this problem, all we need to do is just calculate numbers of points on all possible lines.

To do this, we first check all lines get through point 1. Then we check all lines that get through point 2 but not point 1. By doing this, we can get what we want.

Code in Python:

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        maximum = 0
        for i in xrange(0, len(points)):
            slopes = {'invalid':1}
            same = 0
            for j in xrange(i+1, len(points)):
                if points[i].x == points[j].x and points[i].y == points[j].y:
                    same += 1
                    continue
                if points[i].x == points[j].x:
                    slope = 'invalid'
                else:
                    slope = (points[i].y-points[j].y) * 1. / (points[i].x - points[j].x)
                if slope not in slopes:
                    slopes[slope] = 1
                slopes[slope] += 1
            maximum = max(maximum, max(slopes.values()) + same)
        return maximum

Details:

• The situation that two points with same x and y should be calculated separately.
• We cannot default set new entry in hash as value 0, since the first point is also on that line. New entry should set to be 1 first. (It's apparent we use an entry to represent a line)