Python O(n^3) time/ O(n) space solution


  • 0
    S

    I know there are better solutions. This seems very easy/readable and a little bit different, though.

    Basically: Draw a line between two distinct points and then look for other distinct colinear points. If a,b,c and a,b,d are colinear this means all of them are on the same line.

    def is_collinear(p1, p2, p3):
        return (p2.y - p1.y) * (p3.x - p2.x) == (p3.y - p2.y) * (p2.x - p1.x)
        
    class MyPoint(object):
        def __init__(self, x, y):
            self.x = x
            self.y = y
    
        def __hash__(self):
            return hash((self.x, self.y))
    
        def __eq__(self, other):
            return (self.x, self.y) == (other.x, other.y)
    
        def __repr__(self):
            return "%s:%s" % (self.x, self.y,)
            
    from collections import defaultdict
     
    class Solution(object):
        def maxPoints(self, points):
            W = defaultdict(int)
            r = 0
            for p in points:
                mp = MyPoint(p.x, p.y)
                W[mp] += 1
                r = max(r, W[mp])
    
            P = list(W.keys()) 
            N = len(P)
            for i in range(N):
                for j in range(i+1, N):
                    npc = W[P[i]] + W[P[j]]
                    for k in range(j+1, N):
                        if is_collinear(P[i], P[j], P[k]):
                            npc += W[P[k]]
                    r = max(r, npc)
            return r
    

Log in to reply
 

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