Detect Squares

Examples

Input: add([3,10]); add([11,2]); add([3,2]); count([11,10])
Output: 1

The four points (3,10), (11,2), (3,2), and (11,10) form one axis-aligned square (an 8x8 square), and (11,10) is the query point completing it.

Input: count([14,8]) on the same data
Output: 0

No combination of the stored points, together with (14,8), forms an axis-aligned square.

Input: add([11,2]) again, then count([11,10])
Output: 2

With (11,2) now stored twice, the same square can be completed in two distinct ways - once using each copy of (11,2) - so the count doubles.

Constraints

• point.length == 2

• 0 <= x, y <= 1000

• At most 3000 calls total to add and count combined.

Approach

Any three points of an axis-aligned square, once you know two of them form one full side or one full diagonal, pin down the fourth corner exactly - there's no ambiguity. That means one workable approach is: for the query point, look at every other stored point as a potential diagonal partner. If a point really sits diagonally opposite the query (matching horizontal and vertical distance), the other two corners are fully determined, and you just need to check whether those exact points exist among the stored ones.

The faster approach narrows the search before it even starts: only points that share the query's exact x-coordinate can possibly form a vertical side with it. For each such point, the side length is just the difference in y-coordinates, which immediately tells you the exact (x, y) coordinates the other two corners would need to have. Keeping a hash map of "how many times has this exact point been added" turns checking whether those two corners exist into an instant lookup, and a second map grouping points by x-coordinate keeps the search itself limited to only the points worth considering.

Solutions

Brute Force - Check Every Point as a Diagonal Partner

Store every added point in a plain list (duplicates included). For count(), scan the whole list for a point that's diagonally opposite the query (matching horizontal and vertical distance). For each candidate, the other two corners' coordinates are fixed - check how many times each of those was added by scanning the list again.

class DetectSquares {
  constructor() {
    this.points = []; // every added point, duplicates included
  }

  add(point) {
    this.points.push(point);
  }

  count(point) {
    const [x, y] = point;
    let total = 0;

    for (const [x2, y2] of this.points) {
      const side = Math.abs(x2 - x);

      // A genuine diagonal partner is exactly "side" away in both
      // directions, and isn't the query point's own position.
      if (side === 0 || Math.abs(y2 - y) !== side) continue;

      const otherCornerA = this.countOccurrences(x, y2);
      const otherCornerB = this.countOccurrences(x2, y);

      total += otherCornerA * otherCornerB;
    }

    return total;
  }

  countOccurrences(x, y) {
    let count = 0;
    for (const [px, py] of this.points) {
      if (px === x && py === y) count++;
    }
    return count;
  }
}

Time: add: O(1). count: O(n²), where n is the number of stored points · Space: O(n)

Optimal - Group Points by x-Coordinate, Hash Map Lookups

Keep a hash map of exact point counts, plus a second map grouping points by x-coordinate. For count(), only look at points sharing the query's x-coordinate - each one fixes a potential side length, and the other two corners' exact coordinates, checked with instant hash map lookups instead of scanning everything.

class DetectSquares {
  constructor() {
    this.pointCounts = new Map();  // "x,y" -> how many times added
    this.pointsByX = new Map();    // x -> Map(y -> count)
  }

  add(point) {
    const [x, y] = point;
    const key = x + "," + y;
    this.pointCounts.set(key, (this.pointCounts.get(key) || 0) + 1);

    if (!this.pointsByX.has(x)) {
      this.pointsByX.set(x, new Map());
    }
    const yCounts = this.pointsByX.get(x);
    yCounts.set(y, (yCounts.get(y) || 0) + 1);
  }

  count(point) {
    const [x, y] = point;
    const yCounts = this.pointsByX.get(x);
    if (!yCounts) return 0;

    let total = 0;

    for (const [y2, countY2] of yCounts.entries()) {
      if (y2 === y) continue;

      const side = Math.abs(y2 - y);

      // The square can sit to the right of this vertical edge...
      total += countY2
        * (this.pointCounts.get((x + side) + "," + y) || 0)
        * (this.pointCounts.get((x + side) + "," + y2) || 0);

      // ...or to the left of it.
      total += countY2
        * (this.pointCounts.get((x - side) + "," + y) || 0)
        * (this.pointCounts.get((x - side) + "," + y2) || 0);
    }

    return total;
  }
}

Time: add: O(1). count: O(k), where k is the number of stored points sharing the query's x-coordinate · Space: O(n)