The problem
Points are added one at a time, and the same point may be added more than once. Design add(point) and count(point).
count returns how many ways to choose three added points that, with the query point, form a square with positive area and sides parallel to the axes. Repeated points count as different choices.
Examples
- 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]
Constraints
- 0 ≤ x, y ≤ 1000
- At most 3000 calls in total.
The idea
Store how many times each point was added, grouped by x. A square containing the query (x, y) has exactly one corner straight above or below it, at (x, y₂); that corner fixes the side length d = y₂ − y.
The square then lies to the right or to the left: its last two corners are (x + d, y) and (x + d, y₂), or (x − d, y) and (x − d, y₂). Multiply the three corners’ counts — every combination of copies is a different choice — and add them up. Only the points in the query’s own column are tried.
- Time
- O(1) to add; O(points in the query’s column) to count
- Space
- O(points added)
Solution · every language run against every case
class DetectSquares: def __init__(self): self.col = defaultdict(Counter) # x -> {y -> how many points added there} def add(self, point: List[int]) -> None: x, y = point self.col[x][y] += 1 def count(self, point: List[int]) -> int: x, y = point total = 0 # A point straight above or below the query fixes the side length d; the square then # lies to the right or to the left, and needs its other two corners. for y2, n in self.col[x].items(): d = y2 - y if d == 0: continue for x2 in (x + d, x - d): if x2 in self.col: total += n * self.col[x2][y] * self.col[x2][y2] return total