Detect Squares
Medium · Math & Geometry
Build a small data structure that keeps track of points added on a 2D plane, where points may repeat. It supports two operations: adding a point, and given a query point, counting how many axis-aligned squares can be formed using that query point as one corner and three previously added points as the other three corners. A square counts once for every distinct combination of the other three corner points (so duplicate points at the same coordinates create additional squares), and the square's sides must be parallel to the x and y axes.
Examples
Input: add([3,10]); add([11,2]); add([3,2]); count([11,10]) -> 1; count([14,8]) -> 0; add([11,2]); count([11,10]) -> 2
Output: 1, 0, 2
Why: After adding [3,10], [11,2], [3,2], the point [11,10] forms exactly one axis-aligned square with three of the stored points. [14,8] cannot complete any square with the current points, giving 0. Adding [11,2] again doubles the ways to complete the square with [11,10], giving 2.Constraints
calls to add and count total up to 3000, point coordinates satisfy 0 <= x, y <= 1000
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Detect Squares. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.