930. Axis Squares

Medium3.5 points estimatedDesignHash TableCountingGeometry4 hints
RPby Rohit Parihar

A surveyor records stakes on a flat field. Build AxisSquares with an empty constructor.

add(point) stores a stake at point = [x, y]. The same location may be stored many times, and every copy counts as a separate stake.

count(point) returns in how many ways three stored stakes can be chosen so that together with point they are the four corners of a square whose sides are parallel to the axes and whose side length is positive. Two ways differ if they use different stakes, so duplicates multiply the answer. The query point itself is not stored by the call. A call must not scan all stored stakes.

Example 1

Input:
operations = ["AxisSquares","add","add","add","count","add","count","add","count"]arguments = [[],[[40,40]],[[40,45]],[[45,45]],[[45,40]],[[45,40]],[[45,40]],[[40,45]],[[45,40]]]
Output:
[null,null,null,null,1,null,1,null,2]
Explanation:

Corners (40,40), (40,45) and (45,45) are stored. The query (45,40) completes a square of side 5, so it counts 1. A stake placed at the query location itself changes nothing, and after adding a duplicate of (40,45) there are two ways to pick that corner, so the answer becomes 2.

Example 2

Input:
operations = ["AxisSquares","add","add","add","count"]arguments = [[],[[10,10]],[[10,10]],[[10,10]],[[10,10]]]
Output:
[null,null,null,null,0]
Explanation:

Three copies of the same point never form a square of positive area with the query point, so the answer is 0.

Constraints

0 ≤ x, y ≤ 1000

At most 1000 calls to add and at most 2000 calls in total; the answers fit in a 32-bit int

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(1) add, O(k) count (k distinct points in one column)
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.