Detect Squares
Design a class that stores points on a grid and answers square queries:
: store the pointadd(int[] point) . The same point may be added many times, and each copy counts separately.[x, y] : return the number of ways to choose three stored points that, together with the query point, form an axis-aligned square with positive area.count(int[] point)
Limits: 0 <= x, y <= 1000, and there are at most 3000 calls to addcount
Example 1
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
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]
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|
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]
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])
| Candidate p | |x - qx|, |y - qy| | Valid diagonal? | count[p] × count[x][qy] × count[qx][y] | Running total |
|---|---|---|---|---|
| (3, 10) | 8, 0 | no, distances differ | skipped | 0 |
| (11, 2) | 0, 8 | no, same x as the query | skipped | 0 |
| (3, 2) | 8, 8 | yes | count[3][2] × count[3][10] × count[11][2] = 1 × 1 × 2 = 2 | 2 |
The answer is 2. Before the second add([11, 2])
Java Solution
DetectSquares
- Two structures:
answers "how many copies of (x, y)" in O(1), andcount lists each point once sodistinct does not loop over repeats.count() - Adding a point:
is true only for the first copy, which is when the point joinscount[x][y]++ == 0 .distinct - The diagonal test:
skips p unless both distances are equal and nonzero. Checkingcontinue is enough for nonzero, because the distances are equal.x == qx - 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
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
, which is amortised constant time.ArrayList - 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