Arrays and Hashing Counting and voting

94. Detect Squares

Medium

Points arrive one at a time on a plane. Write a class DetectSquares that stores them and counts the squares they make:

DetectSquares() creates an empty store.
add(point) stores point = [x, y]. The same point can be added many times, and every copy is kept.
count(point) returns the number of ways to choose three stored points that, together with point, are the four corners of a square. The square's sides must be parallel to the x and y axes, and its area must be more than 0.

Two ways are different when they use a different copy of some point. So if one corner of a square was added three times, that square counts three times. The point passed to count does not need to have been added.

Your class is tested by replaying a list of calls on a new, empty DetectSquares. ops[i] names the i-th call, "add" or "count", and points[i] is the point it is called with. The answer is the list of every value that count returns, in the order of the calls.

In C# and Go the methods are Add and Count. Go creates the store with Constructor(), and Rust with DetectSquares::new(). The names in ops are the same in every language.

Example 1

Input: ops = ["add", "add", "add", "count", "count", "add", "count"] points = [[2, 1], [6, 1], [6, 5], [2, 5], [4, 5], [6, 5], [2, 5]]

Output: [1,0,2]

Explanation: (2,5), (2,1), (6,1) and (6,5) are the corners of a square with side 4. No three stored points make a square with (4,5). After (6,5) is added a second time, the square can use either copy, so it counts twice.

Example 2

Input: ops = ["count", "add", "add", "add", "count"] points = [[4, 4], [0, 0], [0, 3], [5, 0], [5, 3]]

Output: [0,0]

Explanation: The first count runs before anything is stored. The last four points make a 5 by 3 rectangle, which is not a square.

Example 3

Input: ops = ["add", "add", "add", "add", "count", "add", "count"] points = [[0, 0], [0, 1000000000], [1000000000, 0], [1000000000, 1000000000], [0, 0], [0, 0], [1000000000, 1000000000]]

Output: [1,2]

Explanation: The four points are the corners of the largest square. A stored copy of the point passed to count is never one of the other three corners. After (0,0) is added again, the square at (1000000000,1000000000) can use either copy of it.

Check your understanding

Work out the answer for this input before you write any code.

ops = ["add", "add", "add", "add", "add", "count"] points = [[1, 1], [1, 1], [4, 1], [4, 4], [4, 4], [1, 4]]

Constraints

1 ≤ ops.length ≤ 5000
Each ops[i] is "add" or "count".
points.length equals ops.length.
points[i] = [x, y]
0 ≤ x, y ≤ 10⁹

Clarifying questions

What you would ask an interviewer before writing any code.