> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Detect Squares Python Solution with Tests

> Tested Python solution for LeetCode 2013 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 2013, Medium. Topics: Array, Hash Table, Design, Counting, Data Stream. [View on LeetCode](https://leetcode.com/problems/detect-squares/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2013   # by problem number
lcpy gen -s detect_squares   # by problem name
```

## 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](https://assets.leetcode.com/uploads/2021/09/01/image.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.
detectSquares.count([14, 8]);  // return 0.
detectSquares.add([11, 2]);    // Adding duplicate points is allowed.
detectSquares.count([11, 10]); // return 2.
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/detect_squares/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/detect_squares/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import Counter


class DetectSquares:
    # Time: O(1) per add
    # Space: O(n) for unique points
    def __init__(self) -> None:
        self.point_counts: Counter[tuple[int, int]] = Counter()

    # Time: O(1)
    # Space: O(1)
    def add(self, point: list[int]) -> None:
        self.point_counts[(point[0], point[1])] += 1

    # Time: O(n) - n unique points
    # Space: O(1)
    def count(self, point: list[int]) -> int:
        qx, qy = point
        total = 0

        for (px, py), count in self.point_counts.items():
            # Look for points on the diagonal: equal nonzero distance on both axes.
            if abs(px - qx) != abs(py - qy) or px == qx:
                continue
            total += count * self.point_counts[(px, qy)] * self.point_counts[(qx, py)]

        return total
```

## Complexity

| Time         | Space                  |
| ------------ | ---------------------- |
| O(1) per add | O(n) for unique points |

## Tags

[NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).