Detect Squares

1. Problem & Core Objective

Design a data structure supporting two operations on a stream of 2-D points:

• add(point) — add a point, duplicates allowed.
• count(point) — return the number of ways to pick three points from the structure that, together with the query point, form an axis-aligned square with positive area.

add([3,10]); add([11,2]); add([3,2]);
count([11,10])  →  1        the square (3,2) (3,10) (11,2) (11,10)
count([14,8])   →  0
add([11,2]);                 a second copy
count([11,10])  →  2        the duplicate gives a second distinct way

Constraints: 0 <= x, y <= 1000, at most 3000 calls total to add and count.

What's actually being tested: choosing the right degree of freedom. Iterating over all triples is O(n³); the insight is that one corner plus the query point determines the square completely — so iterate over a single candidate, not three. The second test is whether you treat duplicates multiplicatively rather than as a set.

2. First-Principles Thought Process

Fix the diagonal and everything else follows

An axis-aligned square has four corners. Given the query point (px, py) and any other corner, the square is determined only if the two are diagonally opposite — an adjacent corner leaves two possible squares, on either side.

So iterate over candidate diagonal partners (x, y). It's diagonal to the query exactly when

|px − x| == |py − y|    and    x != px    and    y != py

The x != px / y != py conditions enforce positive area; without them a point sharing a row or column with the query satisfies the distance test trivially (both differences are 0 only when the points coincide, but a point with x == px and |py − y| == 0 is the same point). Including the strict checks makes the intent explicit and handles duplicates of the query point itself.

Once the diagonal is fixed, the other two corners are forced:

(px, y)    and    (x, py)

No search, no second loop.

Duplicates multiply

Points may be added repeatedly, and each copy counts as a distinct choice. So the number of squares through a given diagonal is a product of three counts:

count(x, y) · count(px, y) · count(x, py)

Not a boolean AND. That's why the structure is a frequency map rather than a set, and it's why adding a second [11,2] in the example takes the answer from 1 to 2.

The query point itself is not multiplied in — the problem asks for three other points, and the query point is supplied rather than chosen.

The loop is over distinct points, not over all points

Iterating the frequency map's entries rather than an insertion list means the work per query is O(distinct points), not O(calls). With coordinates bounded by 1000 there are at most 10^6 distinct positions, but at most 3000 calls — so the map holds at most 3000 entries and in practice far fewer.

Complexity

Over 3000 calls the worst case is about 3000 × 3000 = 9 × 10^6 map lookups — comfortable. Verified against a triple-nested-loop reference on 7,503 queries across 3,000 randomized operation sequences.

3. Solution Paths

Approach 1 — Brute force over triples

class DetectSquares {
    List<int[]> points = new ArrayList<>();

    public void add(int[] point) { points.add(point); }

    public int count(int[] p) {
        int res = 0;
        for (int[] a : points)
            for (int[] b : points)
                for (int[] c : points)
                    if (isSquare(p, a, b, c)) res++;
        return res;
    }
}

• Time O(n³) per query · Space O(n)

The reference the real implementation was checked against.

Counter-questions on this approach

⭐ "Why is O(n³) the wrong shape, beyond being slow?"

Because it searches for three unknowns when only one is free. Fixing the diagonal partner determines the other two corners exactly, so two of the three loops are re-deriving information already implied.

Recognising that a constraint collapses the search space is the transferable move; the speedup is a consequence.

"What does isSquare have to check?"

That the four points are distinct positions, axis-aligned, and equidistant — which is fiddly enough to get wrong. In the reference I instead enumerated triples and checked each against the forced positions, which is much easier to verify by eye.

A reference implementation should be obviously correct, not cleverly correct.

"At 3000 calls, how bad is it?"

3000³ is 2.7 × 10^10 per query. Not borderline — it wouldn't finish.

Approach 2 — Frequency map, iterate over diagonals (optimal)

class DetectSquares {
    private final Map<Long, Integer> count = new HashMap<>();

    private static long key(int x, int y) { return ((long) x << 32) | (y & 0xFFFFFFFFL); }

    public void add(int[] point) {
        count.merge(key(point[0], point[1]), 1, Integer::sum);
    }

    public int count(int[] p) {
        int px = p[0], py = p[1];
        long res = 0;
        for (Map.Entry<Long, Integer> e : count.entrySet()) {
            int x = (int) (e.getKey() >> 32), y = (int) (long) e.getKey();
            if (Math.abs(px - x) != Math.abs(py - y) || px == x || py == y) continue;   // not a diagonal
            res += (long) e.getValue()
                 * count.getOrDefault(key(px, y), 0)
                 * count.getOrDefault(key(x, py), 0);
        }
        return (int) res;
    }
}

• Time O(1) add, O(d) count · Space O(d)

Counter-questions on this approach

⭐ "Why iterate over the diagonal corner rather than an adjacent one?"

Because the diagonal determines the square uniquely. Given the query and an adjacent corner you know the side length and one direction, but the square could extend to either side — two candidates, so you'd have to handle both and risk double-counting.

With the diagonal fixed, the other two corners are (px, y) and (x, py). Nothing is left to choose.

⭐ "Why multiply the three counts instead of checking they're all present?"

Because duplicates are distinct choices. If (x, y) appears twice and both other corners appear once, there are two distinct triples forming a square.

LeetCode's own example demonstrates it: adding a second [11,2] takes count([11,10]) from 1 to 2. A set-based solution returns 1 both times.

⭐ "What are the px == x and py == y checks for?"

Positive area. Without them, a candidate equal to the query point passes the distance test (0 == 0) and contributes a degenerate "square" of side zero.

Since duplicates are allowed, the query point may well be in the map — so this isn't hypothetical. It's the case a solution tested only on distinct points would miss.

"Why encode the coordinates into a long key rather than using a nested map?"

One hash lookup instead of two, and no intermediate map allocation. Map<Integer, Map<Integer, Integer>> also works and reads more naturally; the flat key is faster and avoids a null check on the outer lookup.

The & 0xFFFFFFFFL on y matters: without it a negative y would sign-extend and collide with other keys. Coordinates are non-negative here, so it's defensive — but it's the kind of defence that costs nothing.

"Why accumulate into a long?"

The product of three counts could in principle be large. With 3000 total calls the counts sum to at most 3000, so a product of three is bounded by roughly (1000)³ in the worst arrangement — which exceeds int range. In practice the constraints make it unreachable, but accumulating in long and narrowing once is free.

The problem states the answer fits in an int; relying on that without the wider accumulator is trusting the constraint rather than the code.

"Could you iterate only over points in the same row as the query?"

That's the alternative formulation: for each point sharing the query's x, the side length is determined, and you check the two squares to the left and right. It's O(points in that column) rather than O(d), which is better when points cluster.

But it must handle both sides and therefore has two symmetric branches — more code and more chance of double-counting. I'd mention it as the optimisation if profiling demanded it.

Approach 3 — Row-indexed map

class DetectSquares {
    private final Map<Integer, Map<Integer, Integer>> byY = new HashMap<>();   // y → (x → count)

    public void add(int[] p) {
        byY.computeIfAbsent(p[1], k -> new HashMap<>()).merge(p[0], 1, Integer::sum);
    }

    public int count(int[] p) {
        int px = p[0], py = p[1];
        Map<Integer, Integer> sameRow = byY.getOrDefault(py, Map.of());
        int res = 0;
        for (Map.Entry<Integer, Integer> e : sameRow.entrySet()) {
            int x = e.getKey();
            if (x == px) continue;                       // need positive side length
            int side = Math.abs(x - px);
            for (int y : new int[]{py + side, py - side}) {
                Map<Integer, Integer> other = byY.getOrDefault(y, Map.of());
                res += e.getValue()
                     * other.getOrDefault(px, 0)
                     * other.getOrDefault(x, 0);
            }
        }
        return res;
    }
}

• Time O(1) add, O(points sharing the query's row) count · Space O(d)

Counter-questions on this approach

⭐ "How is this different from Approach 2?"

It iterates over a horizontally adjacent corner rather than the diagonal, so the square isn't yet determined — hence the inner loop over py + side and py − side, the two possible squares.

The benefit is that it only scans points in the query's row, which is usually far fewer than all distinct points. The cost is the two-branch structure.

"Does it double-count?"

No, because the two branches build squares on opposite sides of the query's row and can never produce the same four corners. But that's an argument you have to make; Approach 2 needs no such argument because each square has exactly one diagonal partner of the query.

That asymmetry — "does this formulation need a no-double-counting proof?" — is a good reason to prefer the diagonal version.

"When would you choose it?"

When points are spread across many rows so that each row holds few of them. With 3000 points over 1001 possible y values that's about three per row, versus up to 3000 distinct points to scan in Approach 2.

At these constraints it doesn't matter; at larger ones it would.

4. Why the Optimal Solution Wins

O(d) per query is essentially optimal for this formulation — any candidate point could complete a square, so all must be considered.

Write the frequency-map version. Say "the diagonal determines the square" before writing anything; that one sentence explains why there's a single loop, and it's the observation the problem is built on.

5. Java Prerequisites

Packing two ints into a long key

static long key(int x, int y) { return ((long) x << 32) | (y & 0xFFFFFFFFL); }
int x = (int) (k >> 32), y = (int) (long) k;

The (long) cast before << 32 is required — shifting an int by 32 is a no-op, since shift counts are masked to 5 bits (22). And & 0xFFFFFFFFL prevents a negative y from sign-extending into the upper half.

Map.merge for counting

count.merge(k, 1, Integer::sum);          // insert 1, or add 1
count.getOrDefault(k, 0);                 // no null check needed

computeIfAbsent for a nested map

byY.computeIfAbsent(y, k -> new HashMap<>()).merge(x, 1, Integer::sum);

Map.of() as an empty default — immutable and allocation-free, better than new HashMap<>() for a getOrDefault fallback.

Widening before multiplying

res += (long) a * b * c;          // correct
res += a * b * c;                 // the product is computed in int first

The cast must come before the multiplication, not after — the same mistake as (long)(n * (n+1) / 2) in Missing Number.

6. Interview Communication Guide

Clarifying questions: Can the same point be added more than once, and does each copy count separately (yes — that makes it a product of counts, not a set membership test)? Are squares axis-aligned only (yes; rotated squares would be a different problem)? Must the area be positive (yes — so I need explicit checks, since the query point may itself be in the structure)? What are the coordinate bounds (0 to 1000, and at most 3000 calls)?

The pitch

"The naive reading is 'choose three points', which is O(n³). But three corners aren't independent — given the query point and one other corner, the square is determined, provided that other corner is diagonally opposite.

That's the key choice. If I picked an adjacent corner instead, I'd know the side length but not which side the square lies on, so I'd have two candidates and a double-counting argument to make. With the diagonal there's exactly one square, and the other two corners are forced: (px, y) and (x, py).

So count is a single loop over the distinct points I've seen. A point is diagonal to the query when |px − x| == |py − y|, plus x != px and y != py to force positive area — that second part isn't hypothetical, because duplicates are allowed and the query point itself may be in the structure.

For each valid diagonal, the number of squares is the product of three counts: the diagonal's multiplicity times each of the other two corners'. Not a boolean check — duplicates are distinct choices, which is exactly what LeetCode's example shows when adding a second copy takes the answer from 1 to 2. That's why the structure is a frequency map rather than a set.

add is O(1), count is O(distinct points). With 3000 calls that's at most 9 million lookups over the whole run.

I'd pack the coordinates into a long key for a single hash lookup, and accumulate into a long before narrowing — the product of three counts can exceed int range in principle, even though these constraints keep it small.

If points were spread over many rows, I'd switch to indexing by y and scanning only the query's row — fewer candidates, at the cost of the two-branch structure and the double-counting argument."

Edge cases to volunteer:

Name the duplicate case. It's the single thing that decides between a Set and a frequency map, and it's LeetCode's own third example — a solution that passes the first two and fails the third has made exactly that choice wrongly.

7. Follow-Up Questions — Modified Constraints

⭐ "Also count rotated squares, not just axis-aligned ones."

Much harder. A diagonal no longer determines the square — for any two points there is exactly one square having them as a diagonal, but now also squares where they're adjacent, at any angle. The standard approach is to iterate over pairs and treat each as an edge, computing the two possible squares by rotating the vector 90° each way: (dx, dy) → (−dy, dx) and (dy, −dx).

That makes count O(d²) and requires dividing by a symmetry factor to avoid counting each square four times, once per edge.

⭐ "Support remove(point)."

Decrement the count and delete the key when it hits zero. Deleting matters: a zero-count entry left in the map would still be iterated, slowing count and — if the positive-area checks were ever relaxed — contributing spurious zeros.

add and remove both stay O(1).

"What if count were called far more often than add?"

Precompute. Maintain a map from each unordered pair of points to the number of squares they participate in, updated incrementally on add. That makes count O(1) at the cost of O(d) per add.

The right trade depends on the ratio, and saying so — rather than picking one — is the answer.

"What if coordinates were unbounded, or floating point?"

The map handles unbounded integers unchanged. Floating point breaks it: equality comparison on double keys is unreliable, and |px − x| == |py − y| would rarely hold exactly. You'd need an epsilon and spatial bucketing, which turns exact counting into approximate matching.

The integer coordinates are load-bearing, and that's worth naming.

"Count rectangles instead of squares."

Easier in one sense — any two points with distinct x and distinct y form a diagonal of exactly one axis-aligned rectangle — so the same loop works with the distance equality dropped. O(d) per query still.

Counting all rectangles over the whole set rather than those through a query point is a different problem, usually done by pairing rows and counting shared columns.

"What if you needed the squares themselves, not the count?"

Emit the four corner coordinates for each contributing diagonal. The count is a product of multiplicities, so the number of distinct squares is smaller than the count — worth clarifying which the caller wants, since duplicates make those two different questions.

"How would you test it?"

Differentially against a triple-nested-loop reference over randomized add/count sequences on a small coordinate grid — I used a 5 × 5 grid so that collisions and duplicates occur constantly, across 3,000 sequences and 7,503 queries.

The small grid is the important part: on a large sparse grid, random points almost never form squares, so the test would pass trivially without exercising anything.