6-liner in Python, Simple solution without GCD


  • 1
    O

    Simple math: a line can be uniquely represented by y=ax+b or x=c (vertical-line case).

    We can iterate through all pairs of points and find the line that the 2 points are forming. The hash key tuple for the line is either (a, b) or (float('inf'), c).

    By doing that, all points are grouped by unique lines.

    Then we count the number of unique points for each line and return the maximum.

    class Solution(object):
        def maxPoints(self, points):
            d = collections.defaultdict(set)
            for i in range(1, len(points)):
                for j in range(i):
                    p1, p2 = points[i], points[j]
                    d[(float('inf'), p1.x) if p1.x==p2.x else ((p1.y-p2.y)/float(p1.x-p2.x), (p1.x*p2.y-p2.x*p1.y)/float(p1.x-p2.x))] |= set([p1, p2])
            return max(len(s) for s in d.values()) if len(points)>1 else len(points)
    

    Or the longer but easier-to-read version:

    class Solution(object):
        def maxPoints(self, points):
            d = collections.defaultdict(list)
            for i in range(1, len(points)):
                for j in range(i):
                    p1, p2 = points[i], points[j]
                    if p1.x == p2.x:
                        t = (float('inf'), p1.x)
                    else:
                        t = ((p1.y-p2.y)/float(p1.x-p2.x), (p1.x*p2.y-p2.x*p1.y)/float(p1.x-p2.x))
                    d[t] += [p1, p2]
            return max(len(set(l)) for l in d.values()) if len(points)>1 else len(points)
    

  • 2

    No need for (float('inf'), p1.x), you can just use p1.x. After a few more changes:

        def maxPoints(self, points):
            d = collections.defaultdict(set)
            for p, q in itertools.combinations(points, 2):
                d[p.x if p.x==q.x else ((p.y-q.y)/float(p.x-q.x), (p.x*q.y-q.x*p.y)/float(p.x-q.x))] |= {p, q}
            return max(map(len, d.values())) if len(points)>1 else len(points)
    

    Btw, thanks for the motivation :-D


  • 1
    G

    How does python compare two floating point numbers ?
    you create a pair t that represents the slope and the intersect and use that in your collection, but what happens if you have precision problems ? Can three points map to the same bucket even though they don't lie on the same line ?
    Thanks.


Log in to reply
 

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