LeetCode #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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution:

• Each pair of the points can determine a line with two variables (slope, intersection) identifying it. Therefore, we can traverse all the pairs, and build a hash table with lines information (slope, intersection) as the keys and sets of point indices as values. The line with the longest value (maximum number of points) is the solution.
• Due to computer precision of float or double type, the same line may result in different key (slope, intersection), so we can use two integers (a, b) to represent a rational number x: x=a/b, where the great common divisor of a and b is 1, i.e. gcd(a, b) = 1.
• Time complexity: O(O(gcd)*N^2), where O(gcd) represents the time complexity of calling gcd() once.
• Space complexity: O(N^2)

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

class Solution:
    def maxPoints(self, points0):
        points = [Point(i[0], i[1]) for i in points0]

        if len(points) <= 2:
            return len(points)
        else:
            #from collections import defaultdict
            nmax = 1
            #table = defaultdict(set)
            table = dict()
            for i in range(1,len(points)):
                for j in range(i):
                    out = self.slope_inter(points[i], points[j])
                    if out not in table:
                        table[out] = set([i,j]) 
                    else:
                        table[out].add(i)
                        table[out].add(j)
                    #table[out].add(i)
                    #table[out].add(j)
                    nmax = max(nmax, len(table[out]))
            return nmax

    # The great common divisor
    def gcd(self, a=1, b=1):
        a,b = abs(a), abs(b)
        q = a//b
        r = a%b
        if r == 0:
            return b
        else:
            return self.gcd(a=b, b=r)

    def slope_inter(self, p1, p2):
        #import math
        if p1.x == p2.x:
            return 0, 0, p1.x, 0
        else:
            # use two integers to represent slope
            s1 = int(p2.y-p1.y)
            s2 = int(p2.x-p1.x)
            #ds = math.gcd(s1, s2)
            ds = self.gcd(s1, s2)
            if s1*s2>=0:
                s1 = abs(s1); s2 = abs(s2)
            else:
                s1 = -abs(s1); s2 = abs(s2)

            # use two integers to represent intersection
            i1 = int(p1.y*(p2.x-p1.x) - p1.x*(p2.y-p1.y))
            i2 = int(p2.x-p1.x)
            #di = math.gcd(i1, i2)                
            di = self.gcd(i1, i2)
            if i1*i2 >= 0:
                i1 = abs(i1); i2 = abs(i2)
            else:
                i1 = -abs(i1); i2 = abs(i2)

            return int(s1/ds), int(s2/ds), int(i1/di), int(i2/di)