Detect Squares
Part of Practice: Digits & Points
Design a data structure over 2D lattice points supporting two operations. add(point) stores a point; the same point may be added multiple times, and each copy counts separately. count(point) takes a query point and returns how many axis-aligned squares (sides parallel to the x and y axes, strictly positive area) can be formed using the query point as one corner and three previously added points as the other corners.
Constraints that matter: coordinates are bounded (0 to 1000) and there can be thousands of adds, so count must avoid scanning all triples of stored points.
Examples
- Input:
- add([3,10]), add([11,2]), add([3,2]), then count([11,10])
- Output:
- 1
The three stored points plus the query corner [11,10] form an axis-aligned square with side 8: corners (3,10), (11,10), (3,2), (11,2).
- Input:
- then count([14,8])
- Output:
- 0
No stored point sits diagonal to [14,8] with matching partners, so no square exists.
- Input:
- then add([11,2]) again, and count([11,10])
- Output:
- 2
The corner (11,2) now exists twice, and each copy completes the same square shape, so the square is counted twice.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.