Detect Squares Problem – Algorithm Design, Hash‑Map Solutions, and Complexity Analysis

Tencent released its Q1 2025 financial report, reporting 1800 billion revenue (+13% YoY) and 478 billion net profit (+14% YoY), with a 56% gross margin and 14 billion monthly active users for WeChat/Weixin combined.

The article then presents LeetCode problem 2013 “Detect Squares”, which requires maintaining a data stream of points on an X‑Y plane and, for a query point, counting the number of ways to choose three stored points that together with the query form an axis‑aligned square.

Problem requirements:

Add a point (duplicates allowed).

Given a query point, count valid squares.

Example input and output are shown, illustrating that adding duplicate points affects the count.

Solution approach uses a hash‑table‑of‑hash‑tables (Map<Integer, Map<Integer, Integer>>) to store the frequency of points by their x‑coordinate, enabling O(1) addition and O(k) query where k is the number of distinct y‑coordinates for the query’s x.

Java implementation:

class DetectSquares {
    Map
> row2Col = new HashMap<>();
    public void add(int[] point) {
        int x = point[0], y = point[1];
        Map
col2Cnt = row2Col.getOrDefault(x, new HashMap<>());
        col2Cnt.put(y, col2Cnt.getOrDefault(y, 0) + 1);
        row2Col.put(x, col2Cnt);
    }
    public int count(int[] point) {
        int x = point[0], y = point[1];
        int ans = 0;
        Map
col2Cnt = row2Col.getOrDefault(x, new HashMap<>());
        for (int ny : col2Cnt.keySet()) {
            if (ny == y) continue;
            int c1 = col2Cnt.get(ny);
            int len = y - ny;
            int[] nums = new int[]{x + len, x - len};
            for (int nx : nums) {
                Map
temp = row2Col.getOrDefault(nx, new HashMap<>());
                int c2 = temp.getOrDefault(y, 0), c3 = temp.getOrDefault(ny, 0);
                ans += c1 * c2 * c3;
            }
        }
        return ans;
    }
}

C++ implementation:

class DetectSquares {
public:
    unordered_map
> row2Col;
    void add(vector
point) {
        int x = point[0], y = point[1];
        row2Col[x][y]++;
    }
    int count(vector
point) {
        int x = point[0], y = point[1];
        int ans = 0;
        if (row2Col.find(x) == row2Col.end()) return 0;
        auto &col2Cnt = row2Col[x];
        for (auto &entry : col2Cnt) {
            int ny = entry.first;
            if (ny == y) continue;
            int c1 = entry.second;
            int len = y - ny;
            vector
nxOptions = {x + len, x - len};
            for (int nx : nxOptions) {
                if (row2Col.find(nx) == row2Col.end()) continue;
                auto &temp = row2Col[nx];
                int c2 = temp.count(y) ? temp[y] : 0;
                int c3 = temp.count(ny) ? temp[ny] : 0;
                ans += c1 * c2 * c3;
            }
        }
        return ans;
    }
};

Python implementation:

class DetectSquares:
    def __init__(self):
        self.row2Col = defaultdict(lambda: defaultdict(int))
    def add(self, point: List[int]) -> None:
        x, y = point
        self.row2Col[x][y] += 1
    def count(self, point: List[int]) -> int:
        x, y = point
        ans = 0
        col2Cnt = self.row2Col.get(x, {})
        for ny, c1 in col2Cnt.items():
            if ny == y: continue
            length = y - ny
            for nx in (x + length, x - length):
                temp = self.row2Col.get(nx, {})
                c2 = temp.get(y, 0)
                c3 = temp.get(ny, 0)
                ans += c1 * c2 * c3
        return ans

Array‑based Java version uses a fixed 1010×1010 int matrix for O(1) operations.

Complexity analysis: add operation runs in O(1) time; count operation runs in O(k) where k is the number of distinct y‑coordinates for the query’s x (worst‑case O(N) with N points). Space usage is O(M) where M is the number of distinct points stored.