Detect Squares — LeetCode 2013 Python Solution

The problem

You are given a stream of points on the X-Y plane. Design an algorithm that: Adds new points from the stream into a data structure.

Example

Input

["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]

Output

[null, null, null, null, 1, 0, null, 2]

Explanation

DetectSquares detectSquares = new DetectSquares();

Python solution

class DetectSquares:
    def __init__(self):
        self.cnt = defaultdict(Counter)

    def add(self, point: List[int]) -> None:
        x, y = point
        self.cnt[x][y] += 1

    def count(self, point: List[int]) -> int:
        x1, y1 = point
        if x1 not in self.cnt:
            return 0
        ans = 0
        for x2 in self.cnt.keys():
            if x2 != x1:
                d = x2 - x1
                ans += self.cnt[x2][y1] * self.cnt[x1][y1 + d] * self.cnt[x2][y1 + d]
                ans += self.cnt[x2][y1] * self.cnt[x1][y1 - d] * self.cnt[x2][y1 - d]
        return ans


# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2013. Detect Squares is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems