Detect Squares

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.

30:00

Detect Squares

medium

Topics

Companies

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.

Example 1:

Input: {"operations":["DetectSquares","add","add","add","count"],"values":[[],[[3,10]],[[11,2]],[[3,2]],[[11,10]]]}

Output: [null,null,null,null,1]

Constraints:

$\text{points}[i].\text{length} == 2$
$0 \leq x_i, y_i \leq 1000$
At most $3000$ calls in total to add and count.

Input

arr ={"operations":["DetectSquares","add","add","add","count"],"values":[[],[[3,10]],[[11,2]],[[3,2]],[[11,10]]]}

Initialized DetectSquares data structure

xy

Points Added

Squares Found

0

Variables

No variables to display

DepthFunction Call

Stack empty

0/4