2013. Detect Squares

Design a structure that adds points (duplicates allowed) and, for a query point, counts the ways to choose three stored points that form an axis-aligned square of positive area with it. Input is a LeetCode-style list of operations.

Store how many times each point was added. For a query, loop over distinct points as the diagonal and multiply the three corner counts: diagonal × (x, py) × (px, y).

1class DetectSquares {
2  cnt = new Map<string, number>();
3  add([x, y]: number[]) { this.cnt.set(x + "," + y, (this.cnt.get(x + "," + y) ?? 0) + 1); }
4  count([x, y]: number[]): number {
5    let total = 0;
6    for (const [k, c] of this.cnt) {
7      const [px, py] = k.split(",").map(Number);
8      if (Math.abs(px - x) !== Math.abs(py - y) || px === x) continue;
9      total += c * (this.cnt.get(x + "," + py) ?? 0) * (this.cnt.get(px + "," + y) ?? 0);
10    }
11    return total;
12  }
13}

op = DetectSquares

No points yet.

1 / 0

Space: play/pause · ←/→: step