LeetCode 2013 · Medium · Math & Geometry

Detect Squares

Design a structure that takes points one at a time (duplicates allowed) and, given a query point, counts the ways to pick three stored points that form an axis-aligned square of positive area with it.

O(1)add
O(n)count, n points stored
diagonalfixes the whole square

add x y · count x y · separated by ; · 1–12 calls · x and y: 0 to 14

points the number in a cell is ptsCount · ring = query point · outline = the square being tested

class DetectSquares { private Map<Integer, Integer> ptsCount; // key = x * 1001 + y private List<int[]> pts; public DetectSquares() { ptsCount = new HashMap<>(); pts = new ArrayList<>(); } public void add(int[] point) { int key = point[0] * 1001 + point[1]; ptsCount.merge(key, 1, Integer::sum); pts.add(point); } public int count(int[] point) { int res = 0; int px = point[0]; int py = point[1]; for (int[] p : pts) { int x = p[0]; int y = p[1]; int dx = Math.abs(px - x); int dy = Math.abs(py - y); if (dx != dy || x == px || y == py) { continue; } int a = ptsCount.getOrDefault(x * 1001 + py, 0); int b = ptsCount.getOrDefault(px * 1001 + y, 0); res += a * b; } return res; }}
call
—
pts.size()
0
res
—
returns
—

Why it works

  1. Brute force tries every triple of stored points with the query: O(n³) per count.
  2. The diagonal decides everything: in an axis-aligned square, the corner opposite the query point (px, py) is some (x, y) with |x − px| = |y − py| ≠ 0. Once it is fixed, the other two corners must be exactly (x, py) and (px, y). So loop over stored points as diagonal candidates and look the other two up.
  3. Counts handle duplicates: each copy of the diagonal point appears in pts and is visited once; the other two corners contribute a × b ways, where a and b are their counts. Three copies of a corner make three different squares.
  4. Cost: add is O(1); count is O(n) over the stored list, each lookup O(1) in the hash map. Space O(n).
  5. Pitfall: skip candidates in the query's row or column (x == px or y == py): they give zero-area "squares". And a rectangle with unequal sides must not count, hence the |dx| = |dy| test.