Clean Python Solution With Detailed Explanation


  • 1
    A

    To find maximum points that are collinear (lie on a line), we need to understand when are more than two points collinear.

    Two points are trivially collinear since two points determine a line.

    Three points $x_i=(x_i,y_i,z_i)$ for $i=1, 2, 3$ are collinear iff the ratios of distances satisfy
    $$ x_2-x_1:y_2-y_1:z_2-z_1=x_3-x_1:y_3-y_1:z_3-z_1. $$

    Basic Idea


    We can just maintain a HashMap / Dictionary of slope values and increment its count for every similar value of the slope found as we iterate over the pair of points. For each point we update the maximum number of point count we have seen so far.

    Before we do this, we just need to keep three things in mind:

    1. Points might be vertical in which case calculating the slope would throw DivisionByZero exception. So for such cases, we can just keep a count of verticalPoints separately.
    2. There might be overlapping points. We need to count them separately as well.
    3. Even for the points which are neither vertical, nor overlapping, we will have to deal with fractional quantities and precision might become an issue. Thus, it'd be better to store the fraction $p/q$ in its a HashMap as a tuple. There's another problem in doing so. It isn't necessary that the ratio will always be in its reduced form. So instead of using ratio we reduce pair by their gcd before inserting into the HashMap. Since python does not allow list as a key of dictionary, we will resort to str.
    def gcd(a, b):
        while b:
            a, b = b, a%b
        return a
    
    def maxPoints(points):
        slopeMap = dict()
        num_points = len(points)
        maxPoint = 0
        for i in xrange(num_points):
            verticalPoints = overlapPoints = currMax = 0
            for j in xrange(i + 1, num_points):
                print "(" + str(points[i].x) + "," + str(points[i].y) + ") and (" + str(points[j].x) + "," + str(
                    points[j].y) + ")",
                if (points[i].x == points[j].x and points[i].y == points[j].y):
                    overlapPoints += 1
                    print "| OVERLAP |",
                elif points[i].x == points[j].x:
                    verticalPoints += 1
                    print "| VERT |",
                else:
                    print "| NORM |",
                    slope = [(points[i].y - points[j].y), (points[i].x - points[j].x)]
                    temp = gcd(slope[0], slope[1])
                    slope = [slope[0] / temp, slope[1] / temp]
                    try:
                        slopeMap[str(slope)] += 1
                    except:
                        slopeMap[str(slope)] = 1
                    # update the current max - has the current slope value risen to the top?
                    print "currMax =", currMax, "but slopeMap[slope] = ", slopeMap[str(slope)],
                    currMax = max(currMax, slopeMap[str(slope)])
    
                # has number of vertical points risen even more?
                currMax = max(currMax, verticalPoints)
                print "currMax =", currMax
    
            # maxpoint - the maximum number of collinear points with this point
            maxPoint = max(maxPoint, currMax + overlapPoints + 1)
            print " - Max number of points collinear at this stage are", maxPoint
            slopeMap.clear()
        return maxPoint
    

    Testing


    To test our code, lets write a small test case generator.

    def generateNPoints(N):
        return [Point(random.randint(0,12), random.randint(0,12)) for _ in xrange(N)]
    
    def printPoints(NPoints):
        for point in NPoints:
            print "[" + str(point.x) + "," + str(point.y) + "],",
        print ""
    

    Example

    Test Case:

    [7,4], [5,7], [7,4], [8,6], [0,3], [1,6]
    

    Output

    (7,4) and (5,7) | NORM | currMax = 0 but slopeMap[slope] =  1 currMax = 1
    (7,4) and (7,4) | OVERLAP | currMax = 1
    (7,4) and (8,6) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
    (7,4) and (0,3) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
    (7,4) and (1,6) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
     - Max number of points collinear at this stage are 3 0 1
    (5,7) and (7,4) | NORM | currMax = 0 but slopeMap[slope] =  1 currMax = 1
    (5,7) and (8,6) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
    (5,7) and (0,3) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
    (5,7) and (1,6) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
     - Max number of points collinear at this stage are 3 0 0
    (7,4) and (8,6) | NORM | currMax = 0 but slopeMap[slope] =  1 currMax = 1
    (7,4) and (0,3) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
    (7,4) and (1,6) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
     - Max number of points collinear at this stage are 3 0 0
    (8,6) and (0,3) | NORM | currMax = 0 but slopeMap[slope] =  1 currMax = 1
    (8,6) and (1,6) | NORM | currMax = 1 but slopeMap[slope] =  1 currMax = 1
     - Max number of points collinear at this stage are 3 0 0
    (0,3) and (1,6) | NORM | currMax = 0 but slopeMap[slope] =  1 currMax = 1
     - Max number of points collinear at this stage are 3 0 0
     - Max number of points collinear at this stage are 3 0 0
    3
    

Log in to reply
 

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