Detect Squares

How it works

We want to count how many axis-aligned squares can be formed using the given query point (x1, y1) as one corner.

For an axis-aligned square:

• One side is vertical and one side is horizontal
• If we pick another point (x1, y2) on the same vertical line (same x1), then:
  • the side length is side = y2 - y1
  • this determines where the square’s other x-coordinates must be:
    • x3 = x1 + side (square to the right)
    • x4 = x1 - side (square to the left)

So for each possible vertical partner (x1, y2), we can form up to two squares:

1. Square to the right needs points:
   • (x3, y1) and (x3, y2)
2. Square to the left needs points:
   • (x4, y1) and (x4, y2)

Because points can be added multiple times, the total number of squares is the product of the counts of the required points.

This version uses a nested hash map:

• ptsCount[x][y] = how many times point (x, y) was added which makes counting fast and avoids storing a list of all points.

Steps

Data Structure

• ptsCount: nested hash map
  • outer key: x-coordinate
  • inner key: y-coordinate
  • value: count of that point

add(point)

1. Let the point be (x, y).
2. Increment ptsCount[x][y].

count(point)

1. Initialize res = 0.
2. Let the query point be (x1, y1).
3. Iterate over all y2 such that a point (x1, y2) exists (same x-coordinate):
4. Compute the side length:
   • side = y2 - y1
   • If side == 0, skip (same point, no square)
5. Compute possible horizontal positions:
   • x3 = x1 + side (right square)
   • x4 = x1 - side (left square)
6. Add squares formed to the right:
   • ptsCount[x1][y2] * ptsCount[x3][y1] * ptsCount[x3][y2]
7. Add squares formed to the left:
   • ptsCount[x1][y2] * ptsCount[x4][y1] * ptsCount[x4][y2]
8. Return res.

Complexity

• Time complexity: O(1) for add(), O(n) for count().
• Space complexity: O(n)

Things to watch for

Forgetting to Check Both Diagonal Conditions

A common mistake is only checking that the side lengths are equal (|px - x| == |py - y|) without also verifying that the points are not on the same horizontal or vertical line. Both conditions are necessary for a valid square diagonal.

Not Handling Duplicate Points

The problem allows adding the same point multiple times. Using a set instead of a counter for point tracking will lose count information, causing incorrect results when the same point appears multiple times. The number of squares should multiply by the count of each required corner point.

Confusing Diagonal vs Adjacent Corners

When iterating through stored points to find potential squares, some solutions incorrectly look for adjacent corners instead of diagonal corners. Given the query point (px, py) and a candidate diagonal (x, y), the other two corners must be (x, py) and (px, y), not (px + side, py) and (px, py + side).

from typing import List
from collections import defaultdict

class CountSquares:

    def __init__(self):
        self.ptsCount = defaultdict(lambda: defaultdict(int))

    def add(self, point: List[int]) -> None:
        self.ptsCount[point[0]][point[1]] += 1

    def count(self, point: List[int]) -> int:
        res = 0
        x1, y1 = point
        for y2 in self.ptsCount[x1]:
            side = y2 - y1
            if side == 0:
                continue

            x3, x4 = x1 + side, x1 - side
            res += (self.ptsCount[x1][y2] * self.ptsCount[x3][y1] *
                    self.ptsCount[x3][y2])

            res += (self.ptsCount[x1][y2] * self.ptsCount[x4][y1] *
                    self.ptsCount[x4][y2])
        return res

class CountSquares {
    unordered_map<int, unordered_map<int, int>> ptsCount;

public:
    CountSquares() {}

    void add(vector<int> point) {
        ptsCount[point[0]][point[1]]++;
    }

    int count(vector<int> point) {
        int res = 0;
        int x1 = point[0], y1 = point[1];

        for (auto &[y2, cnt] : ptsCount[x1]) {
            int side = y2 - y1;
            if (side == 0) continue;

            int x3 = x1 + side, x4 = x1 - side;
            res += cnt * ptsCount[x3][y1] * ptsCount[x3][y2];
            res += cnt * ptsCount[x4][y1] * ptsCount[x4][y2];
        }

        return res;
    }
};