Solution to LeetCode 2013 Detect Squares.
LeetCode 2013
Detect Squares (Median). [link]
class DetectSquares(object):
def __init__(self):
# self.Hash = defaultdict(<class 'collections.Counter'>, {10: Counter({3: 1}), 2: Counter({3: 1, 11: 1})})
self.Hash = defaultdict(Counter)
print(self.Hash)
def add(self, point):
"""
:type point: List[int]
:rtype: None
"""
x, y = point
# The key of Hash is y, the value of Hash is a Counter dict of x
self.Hash[y][x] += 1
def count(self, point):
"""
:type point: List[int]
:rtype: int
"""
res = 0
x, y = point
if not y in self.Hash:
return 0
yCount = self.Hash[y] # same y diff x
for col, colCount in self.Hash.items():
if col != y: # diff y
d = col - y
# might be duplicated point, so we need to multiply all counts
res += colCount[x] * yCount[x + d] * colCount[x + d]
res += colCount[x] * yCount[x - d] * colCount[x - d]
return res
