356. Detect Squares

MediumDesign

You are given a stream of points on the X-Y plane. Design an algorithm that: - Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points. - Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area. An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis. Implement the DetectSquares class: - DetectSquares() Initializes the object. - void add(int[] point) Adds a new point point = [x, y] to the data structure. - int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.

Examples

Input: ["DetectSquares","add","add","add","count","count","add","count"] [[],[[3,10]],[[11,2]],[[3,2]],[[11,10]],[[14,8]],[[11,2]],[[11,10]]]

Output: [null,null,null,null,1,0,null,2]

Explanation: count returns the number of axis-aligned squares with positive area using the query as one corner.

Constraints

  • point.length == 2
  • 0 <= x, y <= 1000
  • At most 3000 calls in total will be made to add and count.
Loading...

Run checks all cases above. Submit evaluates all test cases.