52ms Python solution O(N^2) with point dedup

• Basically the same N square solution. Used a map to merge identical points to speed up the double loop.

Running time 52 ms above 100% rest submissions in Python category (I know the float key in hash sucks :-)).

``````# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
if len(points) == 0:
return 0
mm = {}
for p in points:
mm[(p.x,p.y)] = mm.get((p.x,p.y), 0) + 1
P = mm.keys()
if len(P) == 1:
return mm[P[0]]
maxP = 0
for i in xrange(len(P)-1):
slopes,repCnt = {},1
for j in xrange(i+1,len(P)):
dx,dy = P[i][0]-P[j][0],P[i][1]-P[j][1]
if dx == 0:
slope = "#"
elif dy == 0:
slope = 0
else:
slope = float(dy) / dx
slopes[slope] = slopes.get(slope,0) + mm[P[j]]
maxP = max(maxP, mm[P[i]] + max(slopes.values()))
return maxP``````

• This is brilliant!

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