You are given a stream of points on the X-Y plane. Design an algorithm that:
An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis.
Implement the DetectSquares class:
DetectSquares() Initializes the object with an empty data structure.void add(int[] point) Adds a new point point = [x, y] to the data structure.int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.
Example 1:
Input
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Output
[null, null, null, null, 1, 0, null, 2]
Explanation
DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // return 1. You can choose:
// - The first, second, and third points
detectSquares.count([14, 8]); // return 0. The query point cannot form a square with any points in the data structure.
detectSquares.add([11, 2]); // Adding duplicate points is allowed.
detectSquares.count([11, 10]); // return 2. You can choose:
// - The first, second, and third points
// - The first, third, and fourth points
Constraints:
point.length == 20 <= x, y <= 10003000 calls in total will be made to add and count.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.
This approach utilizes a hash map to store the frequency of points.
To add a point, simply increase its count in the map. To count squares, iterate over points that share the same x-coordinate or y-coordinate, calculate potential square corners, and update the count based on available points in the map.
This C solution uses a 2D array to keep track of counts of points at each coordinate. The add function increases the count for a given point, and the count function computes possible squares by checking potential vertices on vertical and horizontal alignments.
Time Complexity: O(n) for counting, where n is the width of the plane (1000 in this case).
Space Complexity: O(max_coords^2) due to the array size.
This approach uses a frequency matrix to store the occurrence of each point in a 2D array format. The solution is similar to the hash map solution but relies on direct index access for storing and querying point counts.
While this approach simplifies access patterns, it can incur significant space usage depending on input constraints.
The implementation in C leverages a 2D array for fast access and storage, allowing for quick checks across potential square formations by the index access method. It avoids additional complexities of hash maps but presumes small constraint limits.
Time Complexity: O(n) via direct index checks for valid squares.
Space Complexity: O(MAX_COORD^2), fixed by coordinate bounds.
We can use a hash table cnt to maintain all the information of the points, where cnt[x][y] represents the count of point (x, y).
When calling the add(x, y) method, we increase the value of cnt[x][y] by 1.
When calling the count(x_1, y_1) method, we need to get three other points to form an axis-aligned square. We can enumerate the point (x_2, y_1) that is parallel to the x-axis and at a distance d from (x_1, y_1). If such a point exists, based on these two points, we can determine the other two points as (x_1, y_1 + d) and (x_2, y_1 + d), or (x_1, y_1 - d) and (x_2, y_1 - d). We can add up the number of schemes for these two situations.
In terms of time complexity, the time complexity of calling the add(x, y) method is O(1), and the time complexity of calling the count(x_1, y_1) method is O(n); the space complexity is O(n). Here, n is the number of points in the data stream.
| Approach | Complexity |
|---|---|
| Use HashMap to Store Point Frequencies | Time Complexity: O(n) for counting, where n is the width of the plane (1000 in this case). |
| Use Frequency Matrix | Time Complexity: O(n) via direct index checks for valid squares. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Point Frequencies | Add: O(1), Count: O(n) | O(n) | General case with dynamic points and unknown coordinate distribution |
| Frequency Matrix | Add: O(1), Count: O(C) | O(C²) | When coordinate range is small and predictable |
Detect Squares - Leetcode Weekly Contest - Problem 2013 - Python • NeetCode • 52,155 views views
Watch 9 more video solutions →Practice Detect Squares with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor