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.

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.

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. 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 == 2
0 <= x, y <= 1000
At most 3000 calls in total will be made to add and count.

Solution

Method 1 – Diagonal Detection with Point Frequency Map

We can store all the points in hashmap, but also the counts as the duplicates are allowed.

Now the important part of coordinate geometry. How do we know if points are making square. We see the diagonal element.

Given p1, try all points p3 (p1 and p3 form diagonal)

To compute count(p1):
- We try all points p3 which together with p1 form the diagonal of non-empty square, it means abs(p1.x-p3.x) == abs(p1.y-p3.y) && abs(p1.x-p3.x) > 0
- Since we have 2 points p1 and p3, we can form a square by computing the positions of 2 remain points p2, p4.
- p2 = (p1.x, p3.y)
- p4 = (p3.x, p1.y)

Intuition

We store all points in a frequency map, allowing duplicates. The key geometric insight is that a square is defined by its diagonal. For a given query point, we try all possible points that could form a diagonal with it. If the absolute difference in x and y coordinates is equal and non-zero, these two points can be diagonally opposite in a square. The other two square corners can be computed directly.

For example, let the query point be $p_1 = (x_1, y_1)$ and another point $p_3 = (x_3, y_3)$ in the data structure. If $|x_1 - x_3| = |y_1 - y_3|$ and $x_1 \neq x_3$ and $y_1 \neq y_3$ , then $p_1$ and $p_3$ can be diagonally opposite corners of a square. The other two corners are $p_1' = (x_1, y_3)$ and $p_3' = (x_3, y_1)$ . The number of squares is the product of the counts of $p_1'$ and $p_3'$ .

Approach

Use a 2D array or map to count occurrences of each point.
For add, increment the count for the given point.
For count, iterate over all points that could form a diagonal with the query point (same distance in x and y, and not zero).
For each diagonal, compute the other two corners and multiply their counts to get the number of squares.
Sum the results for all possible diagonals.

Complexity

⏰ Time complexity: O(1) for add, O(T) for count, where T is the number of points added.
🧺 Space complexity: O(T) in Python, O(1000^2) in C++/Java due to the grid size.

Code

C++

#include <vector>
using namespace std;
class DetectSquares {
    int cntPoints[1001][1001] = {};
    vector<pair<int, int>> points;
public:
    void add(vector<int> point) {
        int x = point[0], y = point[1];
        cntPoints[x][y]++;
        points.emplace_back(x, y);
    }
    int count(vector<int> point) {
        int x1 = point[0], y1 = point[1], ans = 0;
        for (auto& [x3, y3] : points) {
            if (abs(x1 - x3) == abs(y1 - y3) && x1 != x3 && y1 != y3) {
                ans += cntPoints[x1][y3] * cntPoints[x3][y1];
            }
        }
        return ans;
    }
};

Java

class DetectSquares {
    int[][] cntPoints = new int[1001][1001];
    List<int[]> points = new ArrayList<>();
    public void add(int[] point) {
        int x = point[0], y = point[1];
        cntPoints[x][y]++;
        points.add(new int[]{x, y});
    }
    public int count(int[] point) {
        int x1 = point[0], y1 = point[1], ans = 0;
        for (int[] p : points) {
            int x3 = p[0], y3 = p[1];
            if (Math.abs(x1 - x3) == Math.abs(y1 - y3) && x1 != x3 && y1 != y3) {
                ans += cntPoints[x1][y3] * cntPoints[x3][y1];
            }
        }
        return ans;
    }
}

Python

class DetectSquares:
    def __init__(self) -> None:
        self.cntPoints = [[0] * 1001 for _ in range(1001)]
        self.points: list[tuple[int, int]] = []
    def add(self, point: list[int]) -> None:
        x, y = point
        self.cntPoints[x][y] += 1
        self.points.append((x, y))
    def count(self, point: list[int]) -> int:
        x1, y1 = point
        ans = 0
        for x3, y3 in self.points:
            if abs(x1 - x3) == abs(y1 - y3) and x1 != x3 and y1 != y3:
                ans += self.cntPoints[x1][y3] * self.cntPoints[x3][y1]
        return ans