11 lines Python


  • 2
    def maxPoints(self, points):
        answer = 0
        for p in points:
            pctr = 0
            ctr = collections.Counter()
            for q in points:
                x, y = q.x - p.x, q.y - p.y
                pctr += x == y == 0
                ctr[float(y)/x if x else 'inf'] += 1
            ctr['inf'] -= pctr
            answer = max(answer, pctr + max(ctr.values()))
        return answer
    

    For each point p...

    1. Count how often p itself appears.
    2. Count how often each slope through p appears (use 'inf' for vertical lines).
    3. The p-counter plus the largest slope-counter tell the largest number of points on a line through p.

    Maximize the latter over all points p.


    Implementation detail: I count every p towards ctr['inf'] and subtract them afterwards because that's slightly simpler/shorter and because this way, ctr can't be empty (which would give me trouble when asking max(ctr.values())).


  • 0
    L

    @StefanPochmann Won't pass the last test case because of Python's float precision


  • 0

    @livelearn Yeah, that test case was added only recently. Originally I thought floats might be enough and it did get accepted. Not sure what to do with this now. I tried the simple fix of using fractions.Fraction instead of float, but that gets Time Limit Exceeded :-(


  • 2

    Hmm, not sure why Fraction is so slow. Using an equivalent tuple is much faster and gets accepted:

    from fractions import gcd
    
    class Solution(object):
        def maxPoints(self, points):
            answer = 0
            for p in points:
                pctr = 0
                ctr = collections.Counter()
                for q in points:
                    x, y = q.x - p.x, q.y - p.y
                    pctr += x == y == 0
                    g = gcd(x, y)
                    ctr[(y/g, x/g) if x else 'inf'] += 1
                ctr['inf'] -= pctr
                answer = max(answer, pctr + max(ctr.values()))
            return answer
    

Log in to reply
 

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