# Detect Squares
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/detect-squares)
Canonical: https://scaleengineer.com/dsa/problems/detect-squares
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/detect-squares/image0.png) 

**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`.

# Approaches
## List Storage with Diagonal Search
This approach uses a simple `List` to store all the points as they are added. While the `add` operation is very fast, the `count` operation is less efficient because it requires searching through the list to find the necessary points to form a square.
**Time:** `add(point)`: `O(1)`

`count(point)`: `O(M * N)`, where `N` is the total number of points added and `M` is the number of unique points. In the worst case where all points are unique (`M=N`), the complexity is `O(N^2)`. This can be too slow if the number of `count` calls is high or `N` is large. · **Space:** `O(N)` to store all the points in the list. The `count` method temporarily uses an additional `O(M)` space for the `HashSet` of unique points, where `N` is the total number of points and `M` is the number of unique points.
**Pros:** The `add` operation is very fast, `O(1)`.; The implementation is relatively straightforward to understand.
**Cons:** The `count` operation is inefficient, with a time complexity of `O(N^2)` in the worst case.; Repeatedly scanning the list to count points is computationally expensive.; Requires extra space for the `HashSet` within the `count` method.
### Explanation
### Data Structure
A `java.util.List<int[]>` is used to store all points, including duplicates.

### `add(point)` Operation
The `add` operation is straightforward: the new point is simply appended to the end of the list. This is an `O(1)` operation.

### `count(point)` Operation
The `count` operation relies on a geometric property of axis-aligned squares. Given a query point `p1`, any other point `p4` can form a square with `p1` only if it's a diagonal corner. This means `p1` and `p4` must have different x and y coordinates, and the absolute difference of their x-coordinates must equal the absolute difference of their y-coordinates.

The algorithm works as follows:
1. To avoid redundant calculations for duplicate points, we first create a `HashSet` of unique points from our list.
2. We iterate through each unique point `p4` from this set.
3. For each `p4`, we check if it can form a valid diagonal with the query point `p1`.
4. If it's a valid diagonal, we can determine the coordinates of the other two required corners, `p2` and `p3`.
5. The crucial, and time-consuming, step is to then iterate through the entire original list to count the occurrences of `p2`, `p3`, and `p4`.
6. The number of squares that can be formed with this specific diagonal configuration is the product of these counts: `count(p2) * count(p3) * count(p4)`.
7. We sum these products for all valid unique diagonals to get the final answer.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;

class DetectSquares {
    private static class Point {
        int x, y;
        Point(int x, int y) { this.x = x; this.y = y; }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }
        @Override
        public int hashCode() { return Objects.hash(x, y); }
    }

    List<Point> points;

    public DetectSquares() {
        points = new ArrayList<>();
    }
    
    public void add(int[] point) {
        points.add(new Point(point[0], point[1]));
    }
    
    public int count(int[] point) {
        Point p1 = new Point(point[0], point[1]);
        int totalSquares = 0;

        HashSet<Point> uniquePoints = new HashSet<>(points);

        for (Point p4 : uniquePoints) {
            if (p1.x == p4.x || p1.y == p4.y || Math.abs(p1.x - p4.x) != Math.abs(p1.y - p4.y)) {
                continue;
            }

            Point p2 = new Point(p1.x, p4.y);
            Point p3 = new Point(p4.x, p1.y);

            long count2 = 0, count3 = 0, count4 = 0;
            for (Point p : points) {
                if (p.equals(p2)) count2++;
                if (p.equals(p3)) count3++;
                if (p.equals(p4)) count4++;
            }
            totalSquares += count2 * count3 * count4;
        }
        return totalSquares;
    }
}
```
### Algorithm
1.  **`add(int[] point)`**
    *   Add the `point` to a `List<int[]> points`.

2.  **`count(int[] point)`**
    *   Let the query point be `p1 = (x1, y1)`.
    *   Create a `HashSet` of unique points from the `points` list to iterate over.
    *   Initialize `total_squares = 0`.
    *   For each unique point `p4 = (x4, y4)` in the hash set:
        *   Check if `p4` is a valid diagonal to `p1`: `x1 != x4`, `y1 != y4`, and `abs(x1 - x4) == abs(y1 - y4)`.
        *   If it is not a valid diagonal, continue to the next unique point.
        *   If it is a valid diagonal, the other two corners are `p2 = (x1, y4)` and `p3 = (x4, y1)`.
        *   Count the occurrences of `p2`, `p3`, and `p4` in the `points` list. Let these counts be `c2`, `c3`, and `c4` respectively. This requires three separate traversals of the list for each unique diagonal.
        *   Add the product `c2 * c3 * c4` to `total_squares`.
    *   Return `total_squares`.

## Frequency Counting with Hash Map
This approach significantly optimizes the `count` operation by pre-calculating and storing the frequency of each point. Instead of searching a list repeatedly, we can retrieve the count of any point in constant time. Given the coordinate constraints, a 2D array serves as a highly efficient frequency map, but a standard Hash Map also works perfectly.
**Time:** `add(point)`: `O(1)` on average for a HashMap.

`count(point)`: `O(Y)` where `Y` is the number of unique y-coordinates that share the same x-coordinate as the query point. In the worst case, this is `O(N)`, but on average, it can be much faster than iterating through all `N` points. · **Space:** `O(M)` where `M` is the number of unique points stored. For a 2D array implementation, the space is `O(C^2)` where `C` is the maximum coordinate value (1001), which is constant space.
**Pros:** Both `add` and `count` operations are very efficient.; The `count` operation's time complexity is optimal for the problem.; Flexible approach that works well with sparse data.
**Cons:** Requires more complex data structures (nested maps or a large 2D array).; Space complexity depends on the number of unique points, which could be large if coordinate ranges were not bounded.
### Explanation
### Data Structure
We use a data structure to map each point to its frequency. The constraints `0 <= x, y <= 1000` make a 2D array `int[1001][1001]` an excellent choice. `counts[x][y]` will store the number of times the point `(x, y)` has been added. 

Alternatively, a `HashMap` can be used, which is more flexible if coordinate ranges are large or sparse. A nested map `Map<Integer, Map<Integer, Integer>>` is a good way to structure this, mapping an x-coordinate to another map where keys are y-coordinates and values are frequencies.

### `add(point)` Operation
When a point is added, we simply increment its corresponding counter in our frequency map/array. This is an `O(1)` operation.

### `count(point)` Operation
Instead of the diagonal logic, we can iterate through points adjacent to the query point. For a query point `p1`, we can iterate through all stored points `p2` that share the same x-coordinate. The distance between `p1` and `p2` defines the side length `s` of a potential square. With `p1`, `p2`, and `s`, the positions of the other two corners (`p3` and `p4`) are determined. The key improvement is that we can fetch the counts of `p3` and `p4` in `O(1)` time from our frequency map. This avoids expensive searches and leads to a much faster `count` operation.

```java
import java.util.HashMap;
import java.util.Map;

class DetectSquares {
    Map<Integer, Map<Integer, Integer>> counts;

    public DetectSquares() {
        counts = new HashMap<>();
    }
    
    public void add(int[] point) {
        int x = point[0];
        int y = point[1];
        counts.computeIfAbsent(x, k -> new HashMap<>()).merge(y, 1, Integer::sum);
    }
    
    public int count(int[] point) {
        int x1 = point[0];
        int y1 = point[1];
        int totalSquares = 0;

        if (!counts.containsKey(x1)) {
            return 0;
        }

        // Get all points that share the same x-coordinate as the query point
        Map<Integer, Integer> yCounts = counts.get(x1);

        // Iterate through each point p2=(x1, y2) that could form a vertical side with p1
        for (Map.Entry<Integer, Integer> entry : yCounts.entrySet()) {
            int y2 = entry.getKey();
            if (y1 == y2) {
                // p1 and p2 are the same point, cannot form a square with positive area
                continue;
            }

            int side = Math.abs(y1 - y2);
            int count_p2 = entry.getValue();

            // Case 1: Square is to the right of the side p1-p2
            int x3 = x1 + side;
            int count_p3 = getCount(x3, y1);
            int count_p4 = getCount(x3, y2);
            totalSquares += count_p2 * count_p3 * count_p4;

            // Case 2: Square is to the left of the side p1-p2
            x3 = x1 - side;
            count_p3 = getCount(x3, y1);
            count_p4 = getCount(x3, y2);
            totalSquares += count_p2 * count_p3 * count_p4;
        }
        
        return totalSquares;
    }

    private int getCount(int x, int y) {
        if (!counts.containsKey(x)) {
            return 0;
        }
        return counts.get(x).getOrDefault(y, 0);
    }
}
```
### Algorithm
The core idea is to find squares by picking a point `p2` that is vertically aligned with the query point `p1`, which defines a side of a potential square. Then, we calculate where the other two points (`p3`, `p4`) must be and use our frequency map to count how many times they exist.

1.  **Data Structure**: A nested Hash Map, `Map<Integer, Map<Integer, Integer>> counts`, where `counts.get(x).get(y)` stores the frequency of point `(x, y)`.
2.  **`add(int[] point)`**: Update the count for `point` in the nested map. This is an `O(1)` operation on average.
3.  **`count(int[] point)`**:
    *   Let the query point be `p1 = (x1, y1)`.
    *   Initialize `total_squares = 0`.
    *   Get the map of all points that share the same x-coordinate `x1`.
    *   Iterate through each such point `p2 = (x1, y2)`.
    *   If `y1 == y2`, the points are identical, so they cannot form a side. Skip.
    *   The distance `s = abs(y1 - y2)` is the side length of a potential square.
    *   **Case 1: Square extends to the right.** The other two corners must be `p3 = (x1 + s, y1)` and `p4 = (x1 + s, y2)`. Fetch their counts `c3` and `c4` from the map.
    *   The number of squares formed this way is `count(p2) * c3 * c4`. Add this to `total_squares`.
    *   **Case 2: Square extends to the left.** The other two corners must be `p3 = (x1 - s, y1)` and `p4 = (x1 - s, y2)`. Fetch their counts and add the product to `total_squares`.
    *   Return the final `total_squares`.

# Solutions
### Java

```java
class DetectSquares { private Map < Integer , Map < Integer , Integer >> cnt = new HashMap <>(); public DetectSquares () { } public void add ( int [] point ) { int x = point [ 0 ], y = point [ 1 ]; cnt . computeIfAbsent ( x , k -> new HashMap <>()). merge ( y , 1 , Integer: : sum ); } public int count ( int [] point ) { int x1 = point [ 0 ], y1 = point [ 1 ]; if (! cnt . containsKey ( x1 )) { return 0 ; } int ans = 0 ; for ( var e : cnt . entrySet ()) { int x2 = e . getKey (); if ( x2 != x1 ) { int d = x2 - x1 ; var cnt1 = cnt . get ( x1 ); var cnt2 = e . getValue (); ans += cnt2 . getOrDefault ( y1 , 0 ) * cnt1 . getOrDefault ( y1 + d , 0 ) * cnt2 . getOrDefault ( y1 + d , 0 ); ans += cnt2 . getOrDefault ( y1 , 0 ) * cnt1 . getOrDefault ( y1 - d , 0 ) * cnt2 . getOrDefault ( y1 - d , 0 ); } } return ans ; } } /** * Your DetectSquares object will be instantiated and called as such: * DetectSquares obj = new DetectSquares(); * obj.add(point); * int param_2 = obj.count(point); */
```

### CPP

```cpp
class DetectSquares { public: DetectSquares () { } void add ( vector < int > point ) { int x = point [ 0 ], y = point [ 1 ]; ++ cnt [ x ][ y ]; } int count ( vector < int > point ) { int x1 = point [ 0 ], y1 = point [ 1 ]; if ( ! cnt . count ( x1 )) { return 0 ; } int ans = 0 ; for ( auto & [ x2 , cnt2 ] : cnt ) { if ( x2 != x1 ) { int d = x2 - x1 ; auto & cnt1 = cnt [ x1 ]; ans += cnt2 [ y1 ] * cnt1 [ y1 + d ] * cnt2 [ y1 + d ]; ans += cnt2 [ y1 ] * cnt1 [ y1 - d ] * cnt2 [ y1 - d ]; } } return ans ; } private: unordered_map < int , unordered_map < int , int >> cnt ; }; /** * Your DetectSquares object will be instantiated and called as such: * DetectSquares* obj = new DetectSquares(); * obj->add(point); * int param_2 = obj->count(point); */
```

### Python

```python
class DetectSquares : def __init__ ( self ): self . cnt = defaultdict ( Counter ) def add ( self , point : List [ int ]) -> None : x , y = point self . cnt [ x ][ y ] += 1 def count ( self , point : List [ int ]) -> int : x1 , y1 = point if x1 not in self . cnt : return 0 ans = 0 for x2 in self . cnt . keys (): if x2 != x1 : d = x2 - x1 ans += self . cnt [ x2 ][ y1 ] * self . cnt [ x1 ][ y1 + d ] * self . cnt [ x2 ][ y1 + d ] ans += self . cnt [ x2 ][ y1 ] * self . cnt [ x1 ][ y1 - d ] * self . cnt [ x2 ][ y1 - d ] return ans # Your DetectSquares object will be instantiated and called as such: # obj = DetectSquares() # obj.add(point) # param_2 = obj.count(point)
```