Detect Squares - Video Solutions

Problem Overview: You design a data structure that supports two operations: add(point) and count(point). After inserting multiple 2D points, the count query must return how many axis-aligned squares can be formed where the query point is one of the corners.

Approach 1: Use HashMap to Store Point Frequencies (Add: O(1), Count: O(n))

The core idea is to store how many times each point appears. Use a HashMap keyed by coordinates such as (x, y). When you call count(x, y), iterate through all stored points and treat each candidate point as the potential diagonal of a square. A valid diagonal must satisfy |x - px| == |y - py| and must not share the same row or column. Once you identify a diagonal, the other two corners are (x, py) and (px, y). Their frequencies are retrieved from the hash map, and the number of squares contributed by this diagonal is the product of their counts.

This works because an axis-aligned square is uniquely determined by a diagonal pair. The add operation simply increments the stored frequency for the point in O(1) time. The count operation scans all stored points, making it O(n) per query with O(n) space. This approach is flexible, handles duplicate points naturally, and relies on constant-time hash lookups. It heavily uses concepts from hash tables, data structure design, and coordinate-based counting.

Approach 2: Use Frequency Matrix (Add: O(1), Count: O(C))

Since the coordinate range in the problem is small (typically 0–1000), you can store point frequencies in a 2D matrix where freq[x][y] represents how many times a point was added. The add operation increments the cell directly. For the count query, iterate across all possible columns to locate potential square side lengths relative to the query point.

If the query point is (x, y), check candidate points on the same row such as (cx, y). The distance d = cx - x determines possible square positions above and below. The other required points become (x, y + d) and (cx, y + d), or the symmetric positions below the row. Multiply the stored frequencies of these three points to count how many squares exist. This approach runs in O(C) time per query where C is the coordinate range (about 1000) and uses O(C²) space.

Recommended for interviews: The HashMap frequency approach is the expected solution. It shows strong understanding of geometry constraints, frequency counting, and efficient array coordinate handling. Interviewers mainly care about recognizing that a square can be identified using a diagonal and that the remaining corners can be counted with constant-time lookups.