MediumHash Map · Design · Geometry

Detect Squares

Points arrive as a stream. add(point) stores a point; duplicates count as separate points. count(point) returns how many ways to choose three stored points that, together with the query point, form a square with positive area whose sides are parallel to the axes.

add [1,1], [2,2], [1,2]; count [2,1] → 1count [3,3] → 0add [2,2]; count [2,1] → 2

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

The plane

Stored points, the query, and the square being tested

Time and space complexity

n = number of add calls so far (duplicates included). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Write calls as add x y or count x y, separated by commas; up to 14 calls with coordinates from 0 to 15.