Detect Squares

PracticeNeetCode ↗LeetCode ↗

Design a data structure that supports adding points, and — given a query point — counting how many axis-aligned squares can be formed using that query point plus three previously added points.

Example

Key Pointers

• For the query point, any stored point directly above or below it (same x, different y) can be one adjacent corner of a candidate square — the vertical distance to it is the square's side length.
• Given that candidate corner, the two remaining corners must sit at that same side length to the left or right of both points — check both directions, since the square can extend either way.
• Track counts, not just presence — a point can be added more than once, and each duplicate multiplies the number of valid squares through that corner.

Step-by-Step Analysis

1. Maintain a hashmap count mapping (x, y) → number of times added.
2. add(x, y): increment count[(x, y)].
3. count_squares(px, py): for every stored point (x, y) with x == px and y != py, treat it as the vertical-edge partner, with side = y - py.
4. For each horizontal direction nx = px + side and nx = px - side, multiply the counts of (x, y), (nx, py), and (nx, y) together and add to the running total.
5. Sum contributions from every candidate point and return the total.

Complexity

Time: O(n) per query, where n is the number of distinct added points — Space: O(n)

Code

from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.count = defaultdict(int)

    def add(self, point: list[int]) -> None:
        self.count[tuple(point)] += 1

    def count_squares(self, point: list[int]) -> int:
        px, py = point
        total = 0

        for (x, y), c in list(self.count.items()):
            if x != px or y == py:
                continue
            side = y - py
            for nx in (px + side, px - side):
                total += c * self.count[(nx, py)] * self.count[(nx, y)]

        return total

Code Explanation

How the solution above works, piece by piece.

1. count maps each point to how many times it was added (duplicates count separately).
2. count_squares tries every stored point directly above or below the query (same x, different y). That fixes the side length side = y − py.
3. The square can extend left or right: for nx = px ± side, the other corners are (nx, py) and (nx, y).
4. Add count(vertical partner) × count(nx, py) × count(nx, y); a missing corner contributes 0.
5. add is O(1); a query is O(number of distinct stored points).

Visual Walkthrough

Running it on points (3, 10), (11, 2), (3, 2) and query (11, 10):

Video Explanation

NeetCode — Detect Squares, LeetCode 2013