149. Max Points on a Line

Description

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

Idea

The code below is my simple solution for this problem using gcd algorithm to calculate the gradients.

Solution

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

from math import gcd

class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        length = len(points)
        if length <= 2:
            return length
        
        tmp = [{} for i in range(length)]
        res = 2
        for i in range(length):
            # count the number of duplicated points for point i
            duplicate = 1
            for j in range(length):
                if i == j:
                    continue
                # count the gradient
                # same point
                if points[i].y == points[j].y and points[i].x == points[j].x:
                    duplicate += 1
                    continue
                # vertical
                elif points[i].x == points[j].x:
                    gradient = (0, 0)
                else:
                    a = points[i].y - points[j].y
                    b = points[i].x - points[j].x
                    c = gcd(a, b)
                    gradient = (a // c, b // c)      
                if gradient not in tmp[i]:
                    tmp[i][gradient] = 0
                tmp[i][gradient] += 1
            if duplicate == length:
                res = duplicate
                break
            result = max(tmp[i].values()) + duplicate
            res = max(res, result)
        
        return res