TL;DR
Store point multiplicities in a hash map; for each query, iterate distinct points as diagonal corners and multiply the three other corner counts — add O(1), count O(n) over distinct points.
Approach 1 — Naive point list with linear rescans
This is a pure design problem, so there is no classic “brute force algorithm” — the naive design just stores every point in a list and, for each query, tests every distinct point as a diagonal, counting matching corners by scanning the whole list.
from typing import List
class DetectSquares:
def __init__(self):
self.points = []
def add(self, point: List[int]) -> None:
self.points.append((point[0], point[1]))
def count(self, point: List[int]) -> int:
px, py = point
total = 0
for x, y in set(self.points):
if abs(x - px) != abs(y - py) or x == px or y == py:
continue
c_diag = self.points.count((x, y))
c_side1 = self.points.count((px, y))
c_side2 = self.points.count((x, py))
total += c_diag * c_side1 * c_side2
return total
Complexity: add is O(1), but count is O(n²): for each of up to n distinct diagonal candidates it runs three O(n) list.count scans. With 3000 calls this is the bottleneck.
Approach 2 — Counter for O(1) corner lookups
The insight: the only thing count needs about a corner is how many times it appears. Store that directly in a Counter keyed by (x, y), so each corner’s multiplicity is an O(1) lookup instead of an O(n) rescan. Iterating the Counter’s keys visits each distinct point once.
For a query point (px, py) and a candidate diagonal corner (x, y), a valid square needs:
abs(x - px) == abs(y - py) — equal side lengths horizontally and vertically,x != px and y != py — positive area (not on the same row or column).
The remaining two corners are then forced to (px, y) and (x, py), and the number of squares through this diagonal is the product of the three corner counts.
from collections import Counter
from typing import List
class DetectSquares:
def __init__(self):
self.cnt = Counter()
def add(self, point: List[int]) -> None:
self.cnt[(point[0], point[1])] += 1
def count(self, point: List[int]) -> int:
px, py = point
total = 0
for (x, y), c in self.cnt.items():
if abs(x - px) != abs(y - py) or x == px or y == py:
continue
total += c * self.cnt[(px, y)] * self.cnt[(x, py)]
return total
Walkthrough for the example sequence add([3,10]), add([11,2]), add([3,2]), then count([11,10]):
- Query
(px, py) = (11, 10). Iterate stored points:
(3, 10): |3-11| = 8, |10-10| = 0 — unequal, skip.(11, 2): |11-11| = 0 — on the same column, skip.(3, 2): |3-11| = 8 == |2-10| = 8, and 3 != 11, 2 != 10 — valid diagonal. Other corners: (11, 2) count 1, (3, 10) count 1. Contribution 1 * 1 * 1 = 1.
- Total
1. After a second add([11,2]), self.cnt[(11,2)] = 2, so the same diagonal contributes 1 * 2 * 1 = 2.
Complexity: add O(1); count O(D) where D is the number of distinct points (each with O(1) corner lookups). Space O(D).
Common pitfalls
- Forgetting the positive-area condition (
x != px and y != py); the diagonal must be a true diagonal, not a horizontal or vertical offset.
- Only checking
abs(x - px) == abs(y - py) but then reading the wrong two side corners — they are (px, y) and (x, py), sharing one coordinate with the query and one with the diagonal.
- Ignoring duplicate points: you must multiply by each corner’s multiplicity, not treat presence as a boolean.
Pattern takeaway
For geometric-counting queries, fix the degrees of freedom you can (here, the diagonal corner) so the rest of the shape becomes fully determined, then reduce counting to hash-map multiplicity lookups. Storing multiplicities (a Counter) instead of raw items turns repeated O(n) scans into O(1) reads.