Detect Squares
You are given a stream of points consisting of x-y coordinates on a 2-D plane. Points can be added and queried as follows:
- Add - new points can be added to the stream into a data structure. Duplicate points are allowed and should be treated as separate points.
- Query - Given a single query point, count the number of ways to choose three additional points from the data structure such that the three points and the query point form a square. The square must have all sides parallel to the x-axis and y-axis, i.e. no diagonal squares are allowed. Recall that a square must have four equal sides.
Implement the CountSquares class:
CountSquares()Initializes the object.void add(int[] point)Adds a new pointpoint = [x, y].int count(int[] point)Counts the number of ways to form valid squares with pointpoint = [x, y]as described above.
Example 1:
Input:
["CountSquares", "add", [[1, 1]], "add", [[2, 2]], "add", [[1, 2]], "count", [[2, 1]], "count", [[3, 3]], "add", [[2, 2]], "count", [[2, 1]]]
Output:
[null, null, null, null, 1, 0, null, 2]
Explanation:
CountSquares countSquares = new CountSquares();
countSquares.add([1, 1]);
countSquares.add([2, 2]);
countSquares.add([1, 2]);
countSquares.count([2, 1]); // return 1.
countSquares.count([3, 3]); // return 0.
countSquares.add([2, 2]); // Duplicate points are allowed.
countSquares.count([2, 1]); // return 2. Constraints:
point.length == 20 <= x, y <= 1000
Recommended Time & Space Complexity
You should aim for a solution with O(1) time for each add() call, O(n) time for each count() call, and O(n) space, where n is the total number of points.
Hint 1
Initially, we can store the points in a global list for the add() call. For the count() call, a brute force approach would use three nested loops to check other points except for the query point, resulting in an O(n^3) time solution. Can you think of a better way? Maybe you should consider the observation that can be drawn from the diagonal of a square.
Hint 2
In a square's diagonal, the absolute difference between the x-coordinates is equal to the absolute difference between the y-coordinates of the two endpoints, and neither difference can be zero. Using these two points, we can determine the other diagonal endpoints.
Hint 3
We store points in a hash map instead of a list for O(1) lookups, treating duplicate points as one while tracking their frequencies. For the count() function, we iterate through points that, along with the query point, can form a diagonal. Let the query point be (qx, qy) and the other point be (x, y), ensuring they form a diagonal. What could be the other two points? Maybe you should consider the points forming a right-to-left diagonal, treating (qx, qy) as the top-right corner.
Hint 4
The other two points are point1 (x, qy) and point2 (qx, y). For counting, we simply add count of point1 * count of point2 to the result res.