149. Max Points on a Line (HashTable)

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: ----------------------------------------------- HashTable 
--------------------------------------------------------- O(n^2) T, O(n) S
import numpy
class Solution(object):
    def maxPoints(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        res = 0
        for i in range(len(points)):                        # Given point A, we need to calculate all slopes between A and other points
            same = 1
            HashTable = collections.defaultdict(int)
            for j in range(i + 1, len(points)):             # There will be three cases:
                if points[i] == points[j]:                  # 1. Some other point is the same as point A.
                    same += 1
                elif points[i][0] == points[j][0]:          # 2. Some other point has the same x coordinate as point A, 
                                                            #    which will result to a positive infinite slope.
                    HashTable['inf'] += 1                   # IMPORTANT !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                                                            # We CANNOT continue and overlook the 'inf' slope here !!!!!!!!!!!!!
                                                            # because the inf slope(the straight upright line) must also be considered !
                else:                                       # 3. General case. We can calculate slope.
                    slope = numpy.float128(points[i][1] - points[j][1]) / numpy.float128(points[i][0] - points[j][0])
                    '''
                    Why use numpy.float128()? consider Python's precision problem, use a rational fraction type to solve the problem
                    '''
                    HashTable[slope] += 1
            res = max(res, max(HashTable.values()+[0]) + same)    # Why add [0] ??? In case the HashTable is empty: e.x. [[0,0]] 
                                                                  # and max(HashTable.values()) will bring a error
                                                                  # We can store all slopes in a hash table. 
                                                                  # And we find which slope shows up mostly. 
                                                                  # Then add the number of same points to it. 
                                                                  # Then we know the maximum number of points on the same line 
                                                                  # for point A.
        return res                                                # We can do the same thing to point B, point C...
                                                                  # Finally, just return the maximum result 
                                                                  # among point A, point B, point C...