Detect Squares

Detect Squares is a design-and-count problem: you stream points into a data structure, then ask how many axis-aligned squares can be formed using a query point as a corner. The trick is a count map plus a clean way to enumerate the other three corners.

The slow way first

The brute force for count is to try every triple of stored points and test whether they plus the query form a square. That is O(n³) per query and hopeless once points pile up. We need to fix the geometry so a query only does a single pass.

The key observation: an axis-aligned square is pinned down by one diagonal. If we know the query corner and the corner diagonally opposite to it, the other two corners are forced.

The idea: count points, multiply corners

Keep a count map from (x, y) to how many times that point was added. For count((qx, qy)), scan every stored point (dx, dy) and ask: is it a diagonal partner of the query? It is when |dx - qx| == |dy - qy| (equal horizontal and vertical distance) and dx != qx (positive area — no degenerate line).

Given a valid diagonal, the two remaining corners are (dx, qy) and (qx, dy). The number of squares through this diagonal is the product of all four corner counts — and we add that to the total.

Because duplicates are counted, three copies of (0,0) give three distinct squares — the product 3 × 1 × 1 captures that automatically.

Walk through it

Step through the animation. We add (0,0) three times and (0,1), (1,0) once each, so the map holds those counts. The query (1,1) scans the stored points and finds (0,0) as its diagonal (dx = dy = 1). The two missing corners (0,1) and (1,0) are both present, so the square count is 3 × 1 × 1 = 3.

Pseudocode

add(point):
    count[point] += 1            # duplicates allowed
 
count(query qx, qy):
    total = 0
    for each stored point (dx, dy) with count c:
        if |dx - qx| != |dy - qy|: skip   # not on a 45-degree diagonal
        if dx == qx:               skip   # same column -> zero area
        # the two remaining corners are forced
        total += c * count[(dx, qy)] * count[(qx, dy)]
    return total

The Python solution

class DetectSquares:
    def __init__(self):
        self.cnt = collections.Counter()
 
    def add(self, point):
        self.cnt[tuple(point)] += 1
 
    def count(self, point):
        qx, qy = point
        total = 0
        for (dx, dy), c in self.cnt.items():
            if abs(dx - qx) != abs(dy - qy) or dx == qx:
                continue
            total += c * self.cnt[(dx, qy)] * self.cnt[(qx, dy)]
        return total

• self.cnt is a Counter so a missing point reads as 0 instead of raising KeyError.
• add just bumps the count for that exact coordinate — duplicates accumulate.
• In count, we loop over distinct stored points (dx, dy) with multiplicity c.
• Line 12 is the diagonal test: equal |dx| and |dy| deltas, and dx != qx rules out a zero-area (vertical) pair.
• Line 14 multiplies the four corner counts. Missing corners contribute 0, so they zero out cleanly.

Complexity

Here n is the number of distinct points stored. The whole win is reframing the search: instead of hunting for three partners, we anchor on one diagonal and let the count map answer the rest in O(1).

When this pattern shows up

Practice