Detect Squares

MediumMath & GeometryNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

Design a class DetectSquares over a stream of points on a 2-D grid. add(point) stores the point [x, y]; duplicates are allowed, and each copy counts separately. count(point) takes a query point and returns the number of ways to choose three stored points that form, with the query point, an axis-aligned square of positive area. Squares built from different copies of a duplicated point count as different ways.

Examples

DetectSquares(); add([2,2]); add([2,5]); add([5,2]); count([5,5]); count([4,4]) returns 1, 0

[5,5] is the query

With [5,5] as the query, the stored points [2,2], [2,5], and [5,2] complete a square of side 3. No stored points complete a square around [4,4].

DetectSquares(); add([1,1]); add([1,1]); add([1,3]); add([3,1]); count([3,3]) returns 2

Either copy of [1,1] can be the corner opposite the query, so the same square counts twice.

DetectSquares(); add([1,1]); add([1,3]); add([3,1]); add([5,1]); add([5,3]); count([3,3]) returns 2

The query is a corner of two squares: one to its lower left with [1,1] opposite, and one to its lower right with [5,1] opposite.

Constraints

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

Hints

Hint 1

Once you fix one more corner of the square, how many choices remain for the other two?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Store a count for every distinct point in a hash map. For count(qx, qy), treat each distinct stored point (x, y) as the corner diagonally opposite the query. It qualifies only when |x - qx| == |y - qy| and that distance is nonzero. The other two corners are then fixed at (qx, y) and (x, qy), so that diagonal contributes cnt(x, y) * cnt(qx, y) * cnt(x, qy) squares. Sum over every candidate. add is O(1), count is O(p) for p distinct points, and space is O(p).

Time

O(1) add, O(p) count

Space

O(p)

Pitfall

Counting degenerate squares or ignoring duplicates. A candidate with the same x as the query gives zero area and must be skipped, and each corner's count multiplies in, since every copy of a point makes a different square.

Solutions

class DetectSquares {
    // Coordinates are at most 1000, so x * 1001 + y is a unique key.
    private final Map<Integer, Integer> counts = new HashMap<>();
    private final List<int[]> distinct = new ArrayList<>();

    public DetectSquares() {}

    public void add(int[] point) {
        int key = point[0] * 1001 + point[1];
        if (counts.merge(key, 1, Integer::sum) == 1) distinct.add(new int[]{point[0], point[1]});
    }

    public int count(int[] point) {
        int qx = point[0], qy = point[1];
        int total = 0;
        for (int[] p : distinct) {
            int x = p[0], y = p[1];
            if (x == qx || Math.abs(x - qx) != Math.abs(y - qy)) continue;
            total += counts.get(x * 1001 + y)
                * counts.getOrDefault(qx * 1001 + y, 0)
                * counts.getOrDefault(x * 1001 + qy, 0);
        }
        return total;
    }
}

from collections import Counter

class DetectSquares:
    def __init__(self):
        self.counts = Counter()

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

    def count(self, point) -> int:
        qx, qy = point
        total = 0
        for (x, y), c in self.counts.items():
            if x == qx or abs(x - qx) != abs(y - qy):
                continue
            total += c * self.counts.get((qx, y), 0) * self.counts.get((x, qy), 0)
        return total