143.Detect Squares

MediumMath & Geometry · 8/8

LeetCode #2013 Video

Problem

Design a data structure over a stream of points on the X-Y plane that supports:

add(point) — add a point [x, y]. Duplicate points are allowed and count as separate points.
count(point) — given a query point, count the number of ways to choose three stored points so that together with the query point they form an axis-aligned square with positive area.

Axis-aligned means the square's edges are parallel to the x- and y-axes.

Examples

Input:
["DetectSquares","add","add","add","count","count","add","count"]
[[],[[3,10]],[[11,2]],[[3,2]],[[11,10]],[[14,8]],[[11,2]],[[11,10]]]

Output:
[null,null,null,null,1,0,null,2]

Explanation:
count([11,10]) -> 1  : square with (3,10), (11,2), (3,2).
count([14,8])  -> 0  : no square possible.
add([11,2])    -> now (11,2) is stored twice.
count([11,10]) -> 2  : the same square, but either copy of (11,2) can be used.

Input:
["DetectSquares","add","add","add","add","count"]
[[],[[0,0]],[[0,1]],[[1,0]],[[1,1]],[[0,0]]]

Output:
[null,null,null,null,null,1]
Explanation: (0,0) itself was added, but the query point is not taken from storage — the other three corners (0,1), (1,0), (1,1) form one square.

Constraints

point.length == 2
0 <= x, y <= 1000
At most 3000 calls in total are made to add and count.

💡 Key Insight

A square is fixed by the query point (qx, qy) and its diagonal corner (x, y): valid when |x - qx| == |y - qy| != 0. The other two corners are then forced: (qx, y) and (x, qy). So count = sum over stored diagonal candidates of cnt(x, y) · cnt(qx, y) · cnt(x, qy) — a hash map of point frequencies makes each lookup O(1), and iterating only over distinct points (with their counts) handles duplicates correctly.

Brute Force over Triples

Timeadd O(1); count O(p³) worst case, where p = number of stored points.SpaceO(p)

Intuition

Store every added point in a list. For a query, try every ordered triple of stored points and check whether they plus the query form an axis-aligned square. Correct, but cubic in the number of points.

Algorithm

add: append the point to points.
count(q): for each stored point d that is a valid diagonal (equal non-zero side lengths):
- for each stored a equal to (qx, dy) and each stored b equal to (dx, qy), increment the answer.
Return the answer.

Visualization

stored: (3,10), (11,2), (3,2)        query: (11,10)

diagonal candidate (3,2): |3-11| = 8 = |2-10|  ✓
   need (11,2): found 1 copy
   need (3,10): found 1 copy
   -> 1 x 1 = 1 square

Code

java

import java.util.*;

class DetectSquares {
    private final List<int[]> points = new ArrayList<>();

    public DetectSquares() {
    }

    public void add(int[] point) {
        points.add(point);
    }

    public int count(int[] point) {
        int qx = point[0], qy = point[1];
        int result = 0;
        for (int[] d : points) {
            int side = Math.abs(d[0] - qx);
            if (side == 0 || side != Math.abs(d[1] - qy)) continue; // not a diagonal
            for (int[] a : points) {
                if (a[0] != qx || a[1] != d[1]) continue;          // corner (qx, dy)
                for (int[] b : points) {
                    if (b[0] == d[0] && b[1] == qy) result++;     // corner (dx, qy)
                }
            }
        }
        return result;
    }
}

Complexity

Time: add O(1); count O(p³) worst case, where p = number of stored points.
Space: O(p) — the list of points.

Frequency Map + Diagonal ScanOptimal

Timeadd O(1); count O(d), where d = number of distinct points (at most 3000).SpaceO(1001²) for the grid plus O(d) for the list

Intuition

Replace the inner loops with frequency lookups. Keep cnt[x][y] (how many times each point was added) and a list of distinct points. For a query, scan the distinct points as potential diagonals; for each valid one, multiply the three frequencies. Since coordinates are in 0..1000, a int[1001][1001] grid works as the map (a HashMap keyed by x * 1001 + y is equivalent).

Algorithm

add(x, y): if cnt[x][y] == 0, append (x, y) to distinct; then cnt[x][y]++.
count(qx, qy):
- For each (x, y) in distinct:
  - Skip unless |x - qx| == |y - qy| and x != qx.
  - result += cnt[x][y] * cnt[qx][y] * cnt[x][qy].
Return result.

Visualization

After adds: (3,10), (11,2), (3,2), (11,2)

cnt:  (3,10)=1   (11,2)=2   (3,2)=1

query (11,10):
   (3,10): dx=8, dy=0   -> not diagonal
   (11,2): dx=0          -> zero area, skip
   (3,2) : dx=8, dy=8   -> cnt(3,2) * cnt(11,2) * cnt(3,10) = 1 * 2 * 1 = 2
answer = 2

flowchart TD
    Q["query (11,10)"] --> D{"for each distinct (x,y):<br/>abs(x-qx) = abs(y-qy) ≠ 0 ?"}
    D -->|"(3,2) yes"| M["cnt(3,2) · cnt(11,2) · cnt(3,10)"]
    D -->|"(3,10), (11,2) no"| S["skip"]
    M --> R["1 · 2 · 1 = 2"]

Code

java

import java.util.*;

class DetectSquares {
    private final int[][] cnt = new int[1001][1001];      // frequency of each point
    private final List<int[]> distinct = new ArrayList<>(); // each point stored once

    public DetectSquares() {
    }

    public void add(int[] point) {
        int x = point[0], y = point[1];
        if (cnt[x][y] == 0) distinct.add(new int[] {x, y});
        cnt[x][y]++;
    }

    public int count(int[] point) {
        int qx = point[0], qy = point[1];
        int result = 0;
        for (int[] p : distinct) {
            int x = p[0], y = p[1];
            // (x, y) must be the opposite corner of a non-empty square
            if (x == qx || Math.abs(x - qx) != Math.abs(y - qy)) continue;
            result += cnt[x][y] * cnt[qx][y] * cnt[x][qy];
        }
        return result;
    }
}

Complexity

Time: add O(1); count O(d), where d = number of distinct points (at most 3000).
Space: O(1001²) for the grid plus O(d) for the list — or O(d) with a HashMap.

Complexity Comparison

Approach	add	count	Space
Brute Force Triples	O(1)	O(p³)	O(p)
Frequency Map + Diagonal Scan	O(1)	O(d)	O(d) (+ grid)

Common Pitfalls

Allowing x == qx — the "square" then has zero area; the problem requires positive area.
Adding instead of multiplying the three frequencies — duplicates multiply the number of distinct squares.
Iterating over all added points (with repeats) and multiplying by cnt[x][y] — that double-counts duplicates of the diagonal.
Counting the query point from storage — it is supplied by count, not chosen from the stored points.
Checking only x - qx == y - qy without abs — that misses squares in two of the four quadrants.