2013. Detect Squares

Design a data structure that accumulates points on a 2-D grid and, for any query point, counts axis-aligned squares whose one corner is that query point. The key insight: fix any diagonal corner and the other two corners are fully determined — so the answer is a product of three independent point counts.

● MediumHash Map / CountingMath / GeometryDesignTypeScript

PROBLEM What we're solving

Implement DetectSquares with two methods:
• add(point) — record a point (duplicates allowed).
• count(point) — return the number of axis-aligned squares whose one corner is the query point, counting multiplicity from duplicate adds.

Concrete example. After adding [3,10], [11,2], [3,2]:
count([11,10]) → 1. The four corners (3,10)·(11,10)·(3,2)·(11,2) form a valid 8×8 square; all three non-query corners exist exactly once.
count([14,8]) → 0. No square can be formed.

KEY IDEA Fix the diagonal — the other two corners are free

Insight → for an axis-aligned square with one corner at the query point (px, py), choose any diagonal corner (ax, ay) where |ax − px| = |ay − py| ≠ 0. Once the diagonal is fixed, the remaining two corners are uniquely determined: (px, ay) and (ax, py). Count them independently and multiply — the product counts every distinct square built from that diagonal pair.

RECIPE Store counts, iterate diagonals, multiply corners

0 · Data structures. Keep a map pts: Map<"x,y", count> for fast point lookups, and xs: Map<x, Set<y>> to enumerate every distinct x-column quickly.
1 · add(x, y). Increment pts["x,y"] and insert y into xs[x]. O(1).
2 · count(px, py) — outer loop. For each distinct x-coordinate ax ≠ px, let d = ax − px. The side length is |d|.
3 · Inner loop over y-values at ax. For each ay at column ax, check |ay − py| = |d|. Skipping wrong-distance points is the geometry gate — it enforces the square constraint.
4 · Multiply three corner counts. pts[ax,ay] × pts[px,ay] × pts[ax,py] — each factor is the number of ways that corner can independently contribute, so their product is the number of valid squares using this diagonal.
5 · Sum over all valid diagonals. Accumulate into total and return.

Classic confusion → people forget that the query point itself need not be stored — it is the anchor, not a stored point. Only the three other corners are looked up in pts. Multiplying four counts (including the query point) double-counts in a confusing way and gives wrong answers.

COST Complexity & trade-offs

Brute force (all triples)

O(n²) count

Enumerate all pairs of stored points as diagonals — too slow for many queries.

Column-indexed map

O(n) count

n = distinct points. Each count query iterates all stored points once (one per diagonal candidate). add is O(1). Space O(n).

The outer loop runs over distinct x-values, and the inner loop over xs[ax] — together they visit every stored point exactly once. Three Map.get calls per point → O(n) per query.

Pattern transfer →the "fix one element, derive the rest" technique appears in 3Sum (fix one number, two-pointer the rest), Count Squares Submatrices (DP on bottom-right corner), and any problem where choosing two of four unknowns pins the others. The multiplication-of-independent-counts trick is the same idea behind the Rectangle Area family.

RUN IT Fix the diagonal, multiply three corner counts

add points (x,y ; ...)query point

step 0 / 7

STARTBegin: will add 3 points, then query (11,10).

1▶class DetectSquares {
2  // Map from "x,y" -> count of times that point was added
3▶  private pts = new Map<string, number>();
4  // Map from x-coordinate -> set of distinct y-values at that x
5▶  private xs = new Map<number, Set<number>>();
6 
7  add(point: [number, number]): void {
8    const [x, y] = point;
9    const key = `${x},${y}`;
10    this.pts.set(key, (this.pts.get(key) ?? 0) + 1);
11    if (!this.xs.has(x)) this.xs.set(x, new Set());
12    this.xs.get(x)!.add(y);
13  }
14 
15  count(point: [number, number]): number {
16    const [px, py] = point;
17    let total = 0;
18 
19    // Iterate every candidate for the diagonal corner
20    for (const [ax, ays] of this.xs) {
21      if (ax === px) continue;           // must be a different column
22      const d = ax - px;                  // side length (signed)
23 
24      for (const ay of ays) {
25        if (Math.abs(ay - py) !== Math.abs(d)) continue; // must form a square
26 
27        // The four corners are (px,py), (ax,ay), (px,ay), (ax,py)
28        const c1 = this.pts.get(`${ax},${ay}`) ?? 0;   // diagonal
29        const c2 = this.pts.get(`${px},${ay}`) ?? 0;   // same col as query
30        const c3 = this.pts.get(`${ax},${py}`) ?? 0;   // same row as query
31        total += c1 * c2 * c3;
32      }
33    }
34    return total;
35  }
36}

State

total

query anchordiagonal candidateaxis-aligned cornersvalid square / total

slowfast

TYPESCRIPT The solution, annotated

detectSquares.ts
class DetectSquares {
  // Map from "x,y" -> count of times that point was added
  private pts = new Map<string, number>();
  // Map from x-coordinate -> set of distinct y-values at that x
  private xs = new Map<number, Set<number>>();

  add(point: [number, number]): void {
    const [x, y] = point;
    const key = `${x},${y}`;
    this.pts.set(key, (this.pts.get(key) ?? 0) + 1);
    if (!this.xs.has(x)) this.xs.set(x, new Set());
    this.xs.get(x)!.add(y);
  }

  count(point: [number, number]): number {
    const [px, py] = point;
    let total = 0;

    // Iterate every candidate for the diagonal corner
    for (const [ax, ays] of this.xs) {
      if (ax === px) continue;           // must be a different column
      const d = ax - px;                  // side length (signed)

      for (const ay of ays) {
        if (Math.abs(ay - py) !== Math.abs(d)) continue; // must form a square

        // The four corners are (px,py), (ax,ay), (px,ay), (ax,py)
        const c1 = this.pts.get(`${ax},${ay}`) ?? 0;   // diagonal
        const c2 = this.pts.get(`${px},${ay}`) ?? 0;   // same col as query
        const c3 = this.pts.get(`${ax},${py}`) ?? 0;   // same row as query
        total += c1 * c2 * c3;
      }
    }
    return total;
  }
}

Reading it block by block

Lines 3–4 — two data structures. pts maps a "x,y" string key to a count, enabling O(1) lookup of how many times a point was added. xs maps each x-coordinate to the set of distinct y-values at that column — this lets the count loop enumerate candidates without scanning every stored point individually.

Lines 7–12 — add.Increment the string-keyed count (or initialize to 1). Insert the y into the column's set. Both operations are O(1) amortized. Using a string key avoids a nested map and makes lookups in count cheap.

Lines 14–16 — outer loop over columns. Skip ax === px (a zero-width square is not a square). Compute d = ax − px; the side length is |d|. We use the signed difference because the two valid diagonal y-offsets are +|d| and −|d|, and the condition |ay − py| === |d| handles both.

Lines 18–19 — geometry gate. Of the y-values stored at column ax, only those exactly |d| away from py can be diagonal corners. This single check enforces the square constraint without any floating-point arithmetic — everything stays integer.

Lines 22–24 — multiply three corner counts. The query point is the anchor. The three other corners are: the diagonal (ax, ay), and the two axis-aligned ones (px, ay) and (ax, py). Their counts multiply because each corner is chosen independently — it's the combinatorial product rule. total += c1 * c2 * c3.

Complexity → add: O(1). count: O(n) where n = distinct stored points — the double loop visits every point exactly once. Space: O(n) for both maps.

INTERVIEWFollow-ups they'll ask

"What if points can have negative coordinates?" The algorithm is unchanged — the string key "x,y" and the absolute-difference check both work for negative integers. The LeetCode constraint limits to [0, 1000] but the logic generalizes.
"How would you handle duplicate adds efficiently?" The current approach stores a count per key, so duplicates multiply naturally into the product. An alternative is to keep a list and count per query, but that is O(n²).
"Can you count non-axis-aligned squares?" Yes — for a rotated square, the diagonal relationship changes: given two opposite corners (x1,y1) and (x2,y2), the other two are at (x1+dy, y1−dx) and (x2+dy, y2−dx) where dx=x2−x1, dy=y2−y1. Same multiply-count idea applies.
"Why not iterate over all pairs of stored points as diagonals?" That would be O(n²) per query. By fixing one corner as the query point and only iterating stored diagonal candidates, we get O(n).
"What are the edge cases?" Query before any add (returns 0), duplicate points (each duplicate multiplies the count), all points in one column (no square possible, correctly returns 0), query point equals a stored point (still valid — only the three other corners are multiplied).

OPTIMAL Hash Map / Counting

detectSquares.ts
class DetectSquares {
  // Map from "x,y" -> count of times that point was added
  private pts = new Map<string, number>();
  // Map from x-coordinate -> set of distinct y-values at that x
  private xs = new Map<number, Set<number>>();

  add(point: [number, number]): void {
    const [x, y] = point;
    const key = `${x},${y}`;
    this.pts.set(key, (this.pts.get(key) ?? 0) + 1);
    if (!this.xs.has(x)) this.xs.set(x, new Set());
    this.xs.get(x)!.add(y);
  }

  count(point: [number, number]): number {
    const [px, py] = point;
    let total = 0;

    // Iterate every candidate for the diagonal corner
    for (const [ax, ays] of this.xs) {
      if (ax === px) continue;           // must be a different column
      const d = ax - px;                  // side length (signed)

      for (const ay of ays) {
        if (Math.abs(ay - py) !== Math.abs(d)) continue; // must form a square

        // The four corners are (px,py), (ax,ay), (px,ay), (ax,py)
        const c1 = this.pts.get(`${ax},${ay}`) ?? 0;   // diagonal
        const c2 = this.pts.get(`${px},${ay}`) ?? 0;   // same col as query
        const c3 = this.pts.get(`${ax},${py}`) ?? 0;   // same row as query
        total += c1 * c2 * c3;
      }
    }
    return total;
  }
}

Complexity → add: O(1). count: O(n) where n = distinct stored points — the double loop visits every point exactly once. Space: O(n) for both maps.

ALT 1 Brute force — try every stored point as a diagonal

add O(1) · count O(n²) · space O(n)

On each count, scan all pairs of stored points, keep the ones that form an axis-aligned square with the query point, and tally — no column index, just nested loops over the raw point list.

approach-2.ts
class DetectSquares {
  // Just keep every point added, with a count map for O(1) corner lookups.
  private points: [number, number][] = [];
  private pts = new Map<string, number>();

  add(point: [number, number]): void {
    const [x, y] = point;
    this.points.push([x, y]);
    const key = x + ',' + y;
    this.pts.set(key, (this.pts.get(key) ?? 0) + 1);
  }

  count(point: [number, number]): number {
    const [px, py] = point;
    let total = 0;
    const seen = new Set<string>(); // dedupe distinct diagonal corners

    // Try every stored point as the diagonal corner (ax, ay).
    for (const [ax, ay] of this.points) {
      if (ax === px || Math.abs(ax - px) !== Math.abs(ay - py)) continue;
      const diagKey = ax + ',' + ay;
      if (seen.has(diagKey)) continue;
      seen.add(diagKey);

      const c1 = this.pts.get(diagKey) ?? 0;            // diagonal
      const c2 = this.pts.get(px + ',' + ay) ?? 0;      // same col as query
      const c3 = this.pts.get(ax + ',' + py) ?? 0;      // same row as query
      total += c1 * c2 * c3;
    }
    return total;
  }
}

Note → Correct, but every count rescans the entire history, so a run of q queries over n points costs O(q·n)— quadratic when both grow. The column-indexed Map<x, Set<y>> visits the same candidates without the duplicate-point rescans and dedupe bookkeeping.

MNEMONIC The one-liner

"Fix the diagonal, the other two corners are free — multiply their counts and sum."

TRIGGERS When you see _ → reach for _

"count axis-aligned squares with a given corner"	fix diagonal → multiply 3 corner counts
design: add points + query rectangles/squares	pts map + column-indexed xs map
\|dx\| = \|dy\| ≠ 0 condition	enforces equal side lengths → square
duplicate points increase count multiplicatively	store count per key, multiply in product

SKELETON The reusable shape

skeleton.ts
class DetectSquares {
  private pts = new Map<string, number>();
  private xs = new Map<number, Set<number>>();

  add([x, y]: [number, number]): void {
    const key = `${x},${y}`;
    this.pts.set(key, (this.pts.get(key) ?? 0) + 1);
    if (!this.xs.has(x)) this.xs.set(x, new Set());
    this.xs.get(x)!.add(y);
  }

  count([px, py]: [number, number]): number {
    let total = 0;
    for (const [ax, ays] of this.xs) {
      if (ax === px) continue;
      const d = ax - px;
      for (const ay of ays) {
        if (Math.abs(ay - py) !== Math.abs(d)) continue;
        total += (this.pts.get(`${ax},${ay}`) ?? 0)
               * (this.pts.get(`${px},${ay}`) ?? 0)
               * (this.pts.get(`${ax},${py}`) ?? 0);
      }
    }
    return total;
  }
}

FLASHCARDS Tap to flip

How many corners do you iterate over in count(px, py)?

Only the diagonal corner (ax, ay). The query point is the anchor; the other two corners (px, ay) and (ax, py) are derived and looked up directly.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

After add([3,10]), add([11,2]), add([3,2]), what does count([11,10]) return?

QUESTION 02

What is the time complexity of a single count() call with n total stored points?

QUESTION 03

What is the geometry condition that a candidate diagonal corner (ax, ay) must satisfy for query point (px, py)?

QUESTION 04

If add([5,5]) is called twice, how does that affect count() calls that use (5,5) as a corner?

QUESTION 05

Why does count() skip the case ax === px (same x-column as the query point)?

QUESTION 06

In the count method, which three corners are looked up in pts?

QUESTION 07

What data structure best supports iterating all distinct y-values at a given x quickly?

QUESTION 08

#2013 · Detect SquaresStore point counts in a hash map. For each query, enumerate all diagonal candidates with |Δx| = |Δy| and multiply the counts of the four candidate corners — two for each axis-aligned square.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Fix the diagonal — the other two corners are free

RECIPE Store counts, iterate diagonals, multiply corners

COST Complexity & trade-offs

RUN IT Fix the diagonal, multiply three corner counts

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Hash Map / Counting

ALT 1 Brute force — try every stored point as a diagonal

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _