Detect Squares

Detect Squares

What is this problem about?

The Detect Squares interview question asks you to design a data structure that processes a stream of 2D points. You need to implement add(point) to store coordinates and count(point) to find the number of ways to form an axis-aligned square using the given point as one of the corners and three other points from the stored collection.

Why is this asked in interviews?

Google and Meta use this to test your ability to handle spatial data using hash tables. It evaluations your skill in identifying geometry properties (like how to uniquely define a square given two diagonal points) and your ability to optimize lookups in a data stream. It’s a great test of "Counting" logic using multiplication of frequencies.

Algorithmic pattern used

This problem uses Hash Tables and Coordinate Geometry.

1. Store points in a Map<X, Map<Y, Count>> or a single Map<Point, Count>.
2. When count(px, py) is called:
   • Iterate through all points that share the same X-coordinate (px, y).
   • Calculate the potential side length side = abs(y - py).
   • If side > 0, check for the other two points needed to complete the square: (px + side, py) and (px + side, y) OR (px - side, py) and (px - side, y).
3. The number of squares is the product of the frequencies of the three required points.

Example explanation

Points added: (3, 10), (11, 2), (3, 2), (11, 10). Query count(11, 10):

1. Found point sharing same X: (11, 2). Side length = 8.
2. Potential squares require points at (11-8, 10) and (11-8, 2).
3. Check if (3, 10) and (3, 2) exist. Both exist.
4. Total = $freq(11, 2) imes freq(3, 10) imes freq(3, 2)$.

Common mistakes candidates make

• Diagonal vs Axis: Not ensuring the square is axis-aligned.
• Zero Side Length: Counting the query point itself as a second corner, leading to a "square" of side length zero.
• Inefficient Search: Iterating through all stored points instead of just those sharing an X or Y coordinate.

Interview preparation tip

Always use a Hash Map to store point frequencies when dealing with "counting combinations." Geometric properties (like diagonals or sides) often allow you to narrow down the search space to a single dimension.