654. Detect Squares
Build a DetectSquares data structure that tracks points on a 2-D integer grid and answers square-counting queries about them.
add(point)records a new point[x, y]on the grid. The exact same point may be added many times, and every copy is a separate point.count(point)receives a query point[x, y]and returns how many ways you can pick three previously added points that, together with the query point, form the four corners of an axis-aligned square with positive area.
Duplicated points multiply the count: if a needed corner was added k times, it contributes k distinct choices. The query point itself does not need to have been added.
Example 1:
Input: add([1,1]) · add([4,1]) · add([1,4]) · count([4,4]) · count([1,1])
Output: 1, then 0
Explanation: The three added points plus the query (4, 4) form one 3×3 square, so the first count returns 1. Querying (1, 1) needs the opposite corner (4, 4) to have been *added*, and it never was — the second count returns 0.
Example 2:
Input: add([2,2]) · add([5,2]) · add([2,5]) · add([5,2]) · count([5,5])
Output: 2
Explanation: The corner (5, 2) was added twice, so the square {(2,2), (5,2), (2,5), (5,5)} can be completed in two distinct ways — one per copy of (5, 2).
Constraints:
- point = [x, y] with 0 ≤ x, y ≤ 1000
- At most 3000 calls to add and 3000 calls to count
- Squares must be axis-aligned and have positive area (side length ≥ 1)
- Duplicate points are allowed and each copy counts separately
Hints:
An axis-aligned square is fully determined by the query corner plus its diagonally opposite corner: the other two corners are forced to (queryX, diagY) and (diagX, queryY).
So for count, you never need to look at triples — iterate over stored points that could be the diagonal corner (|dx| == |dy|, dx != 0) and multiply the multiplicities of the two forced corners.
Store points in a hash map from (x, y) to how many times it was added; each diagonal candidate then costs two O(1) lookups.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: add([1,1]) · add([4,1]) · add([1,4]) · count([4,4]) · count([1,1])
Expected output: 1, 0