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.In #2013 Detect Squares, we design a structure that stores points on a 2D plane and counts how many axis-aligned squares can be formed with a given query point. The key observation is that valid squares must share the same x or y alignment.
A common strategy uses a hash table to count occurrences of points. Maintain a mapping of coordinates such as (x, y) → frequency, and optionally group points by their x coordinate. When processing a query point (x, y), iterate through points with the same x but different y. The vertical distance between them determines the potential side length of a square.
For each candidate side length d, check whether the other two required points (x + d, y) and (x + d, y2) or their mirrored counterparts exist. Multiply their stored counts to accumulate the number of possible squares. Hash maps make these lookups efficient.
This design keeps add operations constant time and ensures efficient square counting using frequency-based lookups.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Counting with Coordinate Lookup | Add: O(1), Count: O(k) where k is points sharing the same x-coordinate | O(n) for storing point frequencies |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
Maintain the frequency of all the points in a hash map.
Traverse the hash map and if any point has the same y-coordinate as the query point, consider this point and the query point to form one of the horizontal lines of the square.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems similar to Detect Squares appear in FAANG-style interviews because they test hash maps, geometry reasoning, and design of efficient data structures. It evaluates both problem-solving and system design thinking.
Hash tables are the most suitable data structure for this problem. They allow constant-time insertion and lookup of point frequencies, which makes detecting square corners efficient during count queries.
The optimal approach uses a hash map to store the frequency of each point and groups points by their x-coordinate. During a query, you iterate through points with the same x value and check whether the other two corners of a square exist using constant-time lookups.
Frequency counting helps handle duplicate points correctly. When multiple identical coordinates exist, multiplying their counts ensures all valid square combinations are counted accurately.