Detect Squares

Problem Statement

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 point, counts the number of ways to choose three points from the data structure such that the three points and the given 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.

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 one of the vertices.

Examples

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
// The square is formed by points [11,10], [3,10], [3,2], [11,2]

detectSquares.count([14, 8]);  // return 0
// No square can be formed

detectSquares.add([11, 2]);    // Add duplicate point
detectSquares.count([11, 10]); // return 2
// Now we have 2 ways: one using each [11,2]

Constraints

point.length == 2
0 <= x, y <= 1000
At most 3000 calls in total will be made to add and count

Solution Approach

This is a design problem that tests hash table usage and geometric understanding.

Key Insights

Axis-aligned square property: If two points (x1, y1) and (x3, y3) are diagonal corners of an axis-aligned square:
- The side length must be the same in both directions: |x3 - x1| = |y3 - y1|
- The other two corners are at (x1, y3) and (x3, y1)
Count duplicates: We need to track frequency of each point, not just existence
Efficient lookup: Use hash map for O(1) point lookups

Algorithm

Data Structure:

Map<String, Integer> pointCount
// Key: "x,y", Value: frequency of that point

add(point):

Convert point to string key
Increment count in hash map

count(point):

Let query point be (x1, y1)
For each stored point (x3, y3):
- Skip if same x or same y (can't form square)
- Skip if |x3 - x1| ≠ |y3 - y1| (not a square)
- Calculate other two corners: (x1, y3) and (x3, y1)
- If both exist, add count(x1,y3) × count(x3,y1) × count(x3,y3) to result
Return total count

Why multiply frequencies?

If we have:

2 points at (x1, y3)
3 points at (x3, y1)
1 point at (x3, y3)

Then we can form 2 × 3 × 1 = 6 different squares using these points!

Visual Example

For count([11, 10]) with points [3,10], [11,2], [3,2]:

(3,10) -------- (11,10) [query]
  |               |
  |               |
  |               |
(3,2)  -------- (11,2)

Diagonal: (11,10) to (3,2)
Other corners: (3,10) and (11,2)
Side length: |11-3| = |10-2| = 8 ✓

All four corners exist → count = 1

Time & Space Complexity

add(): O(1)
- Hash map insertion
count(): O(n)
- Iterate through all unique points (at most n)
- For each, do O(1) hash lookups
Space: O(n)
- Store all points with frequencies

Java Solution

import java.util.*;

class DetectSquares {
    private Map<String, Integer> pointCount;
    private List<int[]> points;

    public DetectSquares() {
        pointCount = new HashMap<>();
        points = new ArrayList<>();
    }

    public void add(int[] point) {
        String key = point[0] + "," + point[1];
        pointCount.put(key, pointCount.getOrDefault(key, 0) + 1);
        points.add(point);
    }

    public int count(int[] point) {
        int x1 = point[0];
        int y1 = point[1];
        int totalCount = 0;

        // Try each stored point as diagonal corner
        for (int[] p : points) {
            int x3 = p[0];
            int y3 = p[1];

            // Skip if not diagonal (same row or column)
            if (x3 == x1 || y3 == y1) {
                continue;
            }

            // Check if it forms a square (equal side lengths)
            if (Math.abs(x3 - x1) != Math.abs(y3 - y1)) {
                continue;
            }

            // The other two corners
            String corner1 = x1 + "," + y3;
            String corner2 = x3 + "," + y1;
            String corner3 = x3 + "," + y3;

            // Count combinations
            int count1 = pointCount.getOrDefault(corner1, 0);
            int count2 = pointCount.getOrDefault(corner2, 0);
            int count3 = pointCount.getOrDefault(corner3, 0);

            totalCount += count1 * count2 * count3;
        }

        return totalCount;
    }
}

Python Solution

from collections import defaultdict
from typing import List

class DetectSquares:
    def __init__(self):
        self.point_count = defaultdict(int)
        self.points = []

    def add(self, point: List[int]) -> None:
        x, y = point
        self.point_count[(x, y)] += 1
        self.points.append(point)

    def count(self, point: List[int]) -> int:
        x1, y1 = point
        total_count = 0

        # Try each stored point as diagonal corner
        for x3, y3 in self.points:
            # Skip if not diagonal
            if x3 == x1 or y3 == y1:
                continue

            # Check if square (equal side lengths)
            if abs(x3 - x1) != abs(y3 - y1):
                continue

            # Other two corners
            count1 = self.point_count[(x1, y3)]
            count2 = self.point_count[(x3, y1)]
            count3 = self.point_count[(x3, y3)]

            total_count += count1 * count2 * count3

        return total_count

Optimization: Use Unique Points

Instead of iterating all points (including duplicates), iterate only unique points:

class DetectSquares {
    private Map<String, Integer> pointCount;

    public DetectSquares() {
        pointCount = new HashMap<>();
    }

    public void add(int[] point) {
        String key = point[0] + "," + point[1];
        pointCount.put(key, pointCount.getOrDefault(key, 0) + 1);
    }

    public int count(int[] point) {
        int x1 = point[0];
        int y1 = point[1];
        int totalCount = 0;

        // Iterate unique points only
        for (String key : pointCount.keySet()) {
            String[] parts = key.split(",");
            int x3 = Integer.parseInt(parts[0]);
            int y3 = Integer.parseInt(parts[1]);

            if (x3 == x1 || y3 == y1) continue;
            if (Math.abs(x3 - x1) != Math.abs(y3 - y1)) continue;

            int count1 = pointCount.getOrDefault(x1 + "," + y3, 0);
            int count2 = pointCount.getOrDefault(x3 + "," + y1, 0);
            int count3 = pointCount.getOrDefault(key, 0);

            totalCount += count1 * count2 * count3;
        }

        return totalCount;
    }
}

This avoids counting the same diagonal multiple times!

Pattern Recognition

This problem demonstrates:

Design problem pattern
Hash map for frequency counting
Geometric properties (square detection)
Combinatorics (multiplying frequencies)

Common Mistakes

❌ Not counting duplicate points separately
❌ Forgetting to check |dx| = |dy| for square validation
❌ Wrong corner calculation (confusing x and y coordinates)
❌ Not multiplying frequencies of all three other corners
❌ Using complex data structures when simple map suffices
❌ Not handling zero-area squares (same point)
❌ Iterating duplicates instead of unique points in optimization

Tips for Interviews

Clarify: Confirm duplicates are counted separately
Geometry: Draw a square and identify the four corners
Hash key: Explain how you'll store points (e.g., "x,y" string)
Diagonal insight: Explain why you check diagonal points
Frequency multiplication: Explain the counting formula
Complexity: add() is O(1), count() is O(n)
Optimization: Mention iterating unique points vs all points
Edge cases: Single point, no squares, duplicate points

Follow-Up Questions

Q: What if we want to detect rectangles instead of squares?
- A: Similar approach, but remove the |dx| = |dy| constraint
Q: What if squares don't need to be axis-aligned?
- A: Much harder! Need to check all point combinations O(n³)
Q: How to optimize if we have millions of points?
- A: Could use spatial indexing (quadtree, R-tree) for better count() performance
Q: What if we need to delete points?
- A: Decrement frequency, remove from map if reaches 0

Why This Problem?

Tests understanding of:

Data structure design
Hash map usage for frequency counting
Geometric properties of squares
Combinatorial counting
Trade-offs between time and space

This is a practical problem for spatial data structures and geometric queries!

Key Formulas

Square Detection:

Diagonal corners: (x1, y1) and (x3, y3)
Condition: |x3 - x1| = |y3 - y1|
Other corners: (x1, y3) and (x3, y1)

Count Formula:

total = Σ count(x1,y3) × count(x3,y1) × count(x3,y3)
        for all valid diagonal points (x3,y3)

Complexity Comparison

| Operation | Approach | Time | Space | |-----------|----------|------|-------| | add() | Hash Map | O(1) | O(n) | | count() | Iterate all points | O(n) | - | | count() | Iterate unique points | O(unique) | - |

Recommendation: Use unique points iteration for better average-case performance.

Detect Squares

Approach

Detect Squares

Problem Statement

Examples

Example 1:

Constraints

Solution Approach

Key Insights

Algorithm

Why multiply frequencies?

Visual Example

Time & Space Complexity

Java Solution

Python Solution

Optimization: Use Unique Points

Related Problems

Pattern Recognition

Common Mistakes

Tips for Interviews

Follow-Up Questions

Why This Problem?

Key Formulas

Complexity Comparison

Solution