LeetEye LeetEye
Medium Math & Geometry ~5 min

Detect Squares

math-and-geometry detect-squares

Problem

You are given a stream of points on the X-Y plane. Design an algorithm that:

- Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points.
- Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area.

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.

Examples

Example 1
Input: nums = [1,2,3]
Output: result
Key Insight

Fix query point as one corner. For each point with same x, compute potential square corners. Check if both exist.

For query point, check points with same x (or y). Calculate side length, check if the other two corners exist. Multiply counts for duplicates.

How to Approach This Problem

Pattern Recognition: When you see keywords like detect squares math-and-geometry, think Math & Geometry.

Step-by-Step Reasoning

1 For axis-aligned square, edges must be:
Answer: Parallel/perpendicular to axes
"Axis-aligned" means sides are horizontal and vertical.
2 Given two diagonal corners (x1, y1) and (x2, y2), the other two are:
Answer: (x1, y2) and (x2, y1)
For axis-aligned square, diagonal corners share no coordinates. Other two share one with each.
3 (x1, y1) and (x2, y2) form square diagonal if:
Answer: |x1 - x2| == |y1 - y2| != 0
Square has equal side lengths. Diagonal implies equal x and y distances.
4 To count squares for query point p:
Answer: For each point on same x or y, check diagonal
Fix one dimension (same x or same y), other corners are determined.
5 Duplicate points should:
Answer: Increase square count
Multiple copies of a point can form multiple squares with same corners.

Solution

class DetectSquares:
    def __init__(self):
        self.points = defaultdict(int)
        self.x_points = defaultdict(list)  # x -> list of y values
    
    def add(self, point: List[int]) -> None:
        x, y = point
        self.points[(x, y)] += 1
        self.x_points[x].append(y)
    
    def count(self, point: List[int]) -> int:
        x1, y1 = point
        result = 0
        
        # For each point with same x, try to form square
        for y2 in self.x_points[x1]:
            if y2 == y1:
                continue
            
            side = abs(y2 - y1)
            
            # Check two possible squares (left and right)
            for x2 in [x1 + side, x1 - side]:
                count1 = self.points[(x2, y1)]
                count2 = self.points[(x2, y2)]
                result += count1 * count2
        
        return result

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Math & Geometry problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye