Detect Squares

Design a class that stores points on a grid and answers square queries:

Limits: 0 <= x, y <= 1000, and there are at most 3000 calls to add and count in total. This is LeetCode 2013.

Example 1
Input: add([3, 10]), add([11, 2]), add([3, 2]), count([11, 10]), count([14, 8]), add([11, 2]), count([11, 10])
Output: 1, 0, 2
Explanation: after the second copy of [11, 2], either copy can be the bottom right corner, so the same square is counted twice.
Example 2
Input: add([1, 1]), count([1, 1])
Output: 0
Explanation: the only stored point is the query point itself, and a square with side 0 has no area.

How to Think About It

Step 1: Count copies, do not store a list

Duplicates matter only through their number. Keep count[x][y], the number of copies of each point. The coordinates are at most 1000, so a 1001 × 1001 array works and every lookup is O(1).

Step 2: One corner fixes the whole square

Trying every triple of stored points is cubic. Instead, notice that the query point q = (qx, qy) and the corner diagonally opposite to it, p = (x, y), decide the square completely. The other two corners must be (x, qy) and (qx, y).

Step 3: When is p a valid opposite corner?

The square is axis-aligned, so the horizontal and vertical distances from q to p must be equal: |x - qx| == |y - qy|. The area must be positive, so p cannot share the x of q. Equal distances then also rule out a shared y.

Step 4: Multiply the counts

Any copy of p, any copy of (x, qy) and any copy of (qx, y) give a different choice of three points. So one valid p contributes count[x][y] × count[x][qy] × count[qx][y]. A missing corner has count 0 and adds nothing.

Step 5: Enumerate diagonals from the distinct points

Loop over the distinct stored points as candidates for p. Each square is found once, from its one diagonal corner, so nothing is double counted. The query point may lie in any of four directions from p, and the absolute values cover all of them.

Walkthrough

The last call of Example 1, count([11, 10]), after [11, 2] has been added twice.

Candidate p|x - qx|, |y - qy|Valid diagonal?count[p] × count[x][qy] × count[qx][y]Running total
(3, 10)8, 0no, distances differskipped0
(11, 2)0, 8no, same x as the queryskipped0
(3, 2)8, 8yescount[3][2] × count[3][10] × count[11][2] = 1 × 1 × 2 = 22

The answer is 2. Before the second add([11, 2]), the same row gives 1 × 1 × 1 = 1, which is the first output.

Java Solution

DetectSquares counts copies of every point in a grid and, for a query, tries each distinct stored point as the corner diagonally opposite the query.

  • Two structures: count answers "how many copies of (x, y)" in O(1), and distinct lists each point once so count() does not loop over repeats.
  • Adding a point: count[x][y]++ == 0 is true only for the first copy, which is when the point joins distinct.
  • The diagonal test: continue skips p unless both distances are equal and nonzero. Checking x == qx is enough for nonzero, because the distances are equal.
  • The product size: with at most 3000 calls, three corners with 1000 copies each give 109, which still fits in an int.

A common mistake is to drop the x == qx check. Then p can be the query point itself with distance 0 on both axes, a square of no area. In Example 2 that version returns 1 instead of 0.

Java
import java.util.ArrayList;
import java.util.List;

public class DetectSquares {
    private final int[][] count = new int[1001][1001]; // count[x][y]: copies of point (x, y)
    private final List<int[]> distinct = new ArrayList<>(); // each point once

    public DetectSquares() {
    }

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

    public int count(int[] point) {
        int qx = point[0], qy = point[1];
        int ways = 0;
        for (int[] p : distinct) {
            int x = p[0], y = p[1];
            // p must be on a diagonal of the query, at a nonzero distance
            if (Math.abs(x - qx) != Math.abs(y - qy) || x == qx) {
                continue;
            }
            ways += count[x][y] * count[x][qy] * count[qx][y]; // the two remaining corners
        }
        return ways;
    }
}

Complexity

  • add: O(1). It does one array increment and, for a new point only, one append to the ArrayList, which is amortised constant time.
  • count: O(d), where d is the number of distinct points stored so far, at most 3000 here. The loop visits each distinct point once and does three array lookups for a valid diagonal.
  • Space: O(C2 + d), where C = 1001 is the coordinate range. The count grid is allocated in full up front, about 4 MB, and the list adds one entry per distinct point.

Another design that keeps counts instead of scanning stored data is Design Tic-Tac-Toe.