369. Detect Squares

For a query point, a square is fixed once you pick the diagonally-opposite corner. Enumerate stored points as that diagonal corner and multiply the counts of the two remaining corners.

Fix the diagonal

Keep a frequency map of every added point. For count(px, py), a valid axis-aligned square is determined by its diagonal corner (x, y): it must satisfy |x - px| == |y - py| (equal side lengths) and x != px (positive area). The other two corners are then (x, py) and (px, y).

Sum over all stored points as the diagonal corner:

res += cnt[(x, y)] * cnt[(x, py)] * cnt[(px, y)]

Worked example

With points (3,10), (11,2), (3,2) added, count(11,10) finds diagonal (3,2): corners (3,10), (11,2) both present → 1 square. After adding a second (11,2), count(11,10) → 2.

Complexity

• Time: add O(1); count O(n) over stored points.
• Space: O(n).

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class DetectSquares {
    private Map<Long, Integer> cnt = new HashMap<>();
    private List<int[]> points = new ArrayList<>();

    public DetectSquares() {
    }

    public void add(int[] point) {
        cnt.merge(enc(point[0], point[1]), 1, Integer::sum);
        points.add(point);
    }

    public int count(int[] point) {
        int px = point[0], py = point[1];
        int res = 0;
        for (int[] p : points) {
            int x = p[0], y = p[1];
            if (Math.abs(x - px) == Math.abs(y - py) && x != px) {
                res += cnt.getOrDefault(enc(x, py), 0) * cnt.getOrDefault(enc(px, y), 0);
            }
        }
        return res;
    }

    private long enc(int x, int y) {
        return (long) x * 100000L + y;
    }
}