Detect Squares (LC 2013)

Problem Statement

Design a data structure that supports adding integer points and counting the number of axis-aligned squares that can be formed with a given query point, using already-added points as the other three corners.

Implement:

• add(point) — add a point [x, y] to the structure (duplicates allowed).
• count(point) — return the number of axis-aligned squares with point as one corner and the other three corners already in the structure.

Example:

DetectSquares detector = new DetectSquares();
detector.add([3,10]);
detector.add([11,2]);
detector.add([3,2]);
detector.count([11,10]); // returns 1 — the square (3,10),(11,10),(11,2),(3,2)
detector.count([14,8]);  // returns 0
detector.add([11,2]);    // duplicates allowed
detector.count([11,10]); // returns 2 — you can choose either (11,2)

Constraints:

• 0 <= x, y <= 1000
• Up to 3000 calls total.

Difficulty: Medium

---

Pattern Recognition

• Input structure: streaming points with repeats.
• What are we counting? completed axis-aligned squares.
• Pattern: hash-map of point counts; iterate over candidate "diagonal" corners.
• Why: given a query point (qx, qy), any axis-aligned square with it as a corner has a unique diagonal corner (dx, dy) satisfying |dx - qx| == |dy - qy| and both are nonzero. Once you fix the diagonal, the other two corners are determined: (qx, dy) and (dx, qy).

This problem is Google-flavored because the naive count is O(n^2) over all pairs but the efficient version is O(|distinct points|) per query.

---

Approach

Brute Force — For Each Point Pair

On count, loop over every added point, try to treat it as the diagonal corner, verify the other two. If you iterate over n added points (including duplicates), you do a lot of redundant work.

Optimal — Count Map + Iterate Distinct Points

Key Insight: Store a map count[(x, y)] = multiplicity. On count((qx, qy)):

• For each distinct (dx, dy) in the map with dx != qx and abs(dx - qx) == abs(dy - qy):
  • Contribute count[(dx, dy)] * count[(qx, dy)] * count[(dx, qy)] to the total.

You pick one diagonal corner, and multiplicities of the other two complete the square.

count((qx, qy)):
    total = 0
    for each (px, py) in points:
        if px == qx: continue           // same x → not a diagonal corner
        if abs(px - qx) != abs(py - qy): continue
        total += count[(px, py)] * count[(qx, py)] * count[(px, qy)]
    return total

Time per count: O(D) where D = distinct points added. Time per add: O(1). Space: O(D).

Note: we skip px == qx (and equivalently require py != qy because of the absolute-value equality), which ensures the square has nonzero area.

---

Walkthrough

Add (3,10), (11,2), (3,2), (11,2).

Map: {(3,10): 1, (11,2): 2, (3,2): 1}.

count((11, 10)):

• Check (3, 10): px=3 != qx=11 ✓; |3-11|=8, |10-10|=0. Not equal, skip.
• Check (11, 2): px=11 == qx, skip.
• Check (3, 2): px=3 != 11 ✓; |3-11|=8, |2-10|=8. Match!
  • count[(3,2)] * count[(11,2)] * count[(3,10)] = 1 * 2 * 1 = 2. Add 2.

Total: 2.

Wait — problem says first count((11,10)) is 1 (before the second add), and after duplicate add it becomes 2. Yes, that matches.

---

Implementation

TypeScript

class DetectSquares {
    private countMap = new Map<string, number>();
    private points: [number, number][] = [];

    private key(x: number, y: number): string { return `${x},${y}`; }

    add(point: number[]): void {
        const k = this.key(point[0], point[1]);
        if (!this.countMap.has(k)) this.points.push([point[0], point[1]]);
        this.countMap.set(k, (this.countMap.get(k) || 0) + 1);
    }

    count(point: number[]): number {
        const [qx, qy] = point;
        let total = 0;
        for (const [px, py] of this.points) {
            if (px === qx) continue;
            if (Math.abs(px - qx) !== Math.abs(py - qy)) continue;
            const diag = this.countMap.get(this.key(px, py)) || 0;
            const left = this.countMap.get(this.key(qx, py)) || 0;
            const right = this.countMap.get(this.key(px, qy)) || 0;
            total += diag * left * right;
        }
        return total;
    }
}

C++

class DetectSquares {
    unordered_map<long long, int> countMap;
    vector<pair<int,int>> points;
    long long key(int x, int y) { return (long long)x * 100003LL + y; }
public:
    void add(vector<int> point) {
        long long k = key(point[0], point[1]);
        if (countMap.find(k) == countMap.end()) {
            points.push_back({point[0], point[1]});
        }
        countMap[k]++;
    }
    int count(vector<int> point) {
        int qx = point[0], qy = point[1];
        int total = 0;
        for (auto& p : points) {
            int px = p.first, py = p.second;
            if (px == qx) continue;
            if (abs(px - qx) != abs(py - qy)) continue;
            int diag = countMap[key(px, py)];
            int left = countMap[key(qx, py)];
            int right = countMap[key(px, qy)];
            total += diag * left * right;
        }
        return total;
    }
};

Watch out:

1. Forgetting to filter px == qx or equivalently py == qy counts degenerate zero-area "squares."
2. Maintain a separate points list for distinct entries so iteration is on unique points, not all adds. Otherwise duplicates cause double-counting.
3. Integer overflow on products for C++ — stay in int given constraints (counts ≤ 3000, so 3000^3 is huge but actually the per-corner count is small, typical products fit easily).

---

Complexity Analysis

	add	count	Space
Brute (iterate adds)	O(1)	O(A) (total adds)	O(A)
Distinct iteration	O(1)	O(D) (distinct points)	O(D)

Bottleneck: each count iterates distinct points; with 3000 ops max, this is trivially fast.

---

Edge Cases

1. No points added — count returns 0; loop runs zero times.
2. Query point itself in map — fine; the px == qx guard excludes it from diagonal role.
3. Duplicates — multiplicities multiply; add twice means two contributions via that slot.
4. Very sparse plane — space proportional to distinct adds; never explodes.
5. Collinear points only — no squares; absolute-value check filters everything.
6. Exactly one square possible — product 1 * 1 * 1 = 1 at the single diagonal match.

---

Related Problems

• LC 447 — Number of Boomerangs — Point-counting based on distance buckets.
• LC 149 — Max Points on a Line — Pair-based line counting; similar pattern density.
• LC 1152 — Analyze User Website Visit Pattern — Count tuples via hashing.
• LC 1948 — Delete Duplicate Folders in System — Hash on structure, not pattern-related but design-heavy like this one.

---

What Is Expected at Each Level

Junior: Reaches a brute force that iterates pair combinations. Might count degenerate squares.

Mid-level: Uses the diagonal-corner trick, proper multiplicity handling, and filters the zero-area case.

Senior (L4 target): Writes the O(D) count method, maintains a distinct-points list for iteration, explains the combinatorial product cleanly, and discusses how you would shard the map for a much larger point stream (e.g., by quadrant or by x bucket).