#2013

Detect Squares

specialist · 860 · lc medium +31 · 52.3% accepted · 1,007 likes · top 42%

Description

Design the DetectSquares class to handle a dynamic stream of 2D points (duplicates allowed). Support two operations:
- void add(int[] point) — insert the point [x, y] into the data structure.
- int count(int[] point) — given a query point [x, y], return the number of ways to select three additional points from the stored data such that together with the query point they form an axis-aligned square with positive area (both sides parallel to the axes).

Example 1:

Input

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

[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]

Output

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

Example 2:

Explanation

DetectSquares detectSquares = new DetectSquares();

detectSquares.add([3, 10]);

detectSquares.add([11, 2]);

detectSquares.add([3, 2]);

detectSquares.count([11, 10]); // return 1. You can choose:

// - The first, second, and third points

detectSquares.count([14, 8]); // return 0. The query point cannot form a square with any points in the data structure.

detectSquares.add([11, 2]); // Adding duplicate points is allowed.

detectSquares.count([11, 10]); // return 2. You can choose:

// - The first, second, and third points

// - The first, third, and fourth points

Code

class DetectSquares:

    def __init__(self):
        

    def add(self, point: List[int]) -> None:
        

    def count(self, point: List[int]) -> int:
        


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

class DetectSquares:

    def __init__(self):
        

    def add(self, point: List[int]) -> None:
        

    def count(self, point: List[int]) -> int:
        


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