Appearance
4.28.8 — Detect Squares
LeetCode 2013 · Medium
The problem
Design a structure with two operations:
add(point)— add a point, possibly a duplicate.count(point)— count how many axis-aligned squares can be formed with the given point as one corner and three previously added points as the others.
add([3,10]); add([11,2]); add([3,2])
count([11,10]) → 1
count([14,8]) → 0The pattern
An axis-aligned square has sides parallel to the axes, which is a strong constraint: given one corner and the diagonally opposite corner, the other two are completely determined.
If the query point is (x, y) and the diagonal corner is (dx, dy), then for the four points to form a square you need:
|dx - x| = |dy - y| \quad \text{and} \quad dx \ne x
The side length is that shared distance, and the remaining two corners are:
(x, dy) \quad\text{and}\quad (dx, y)
Reading those two off the picture is the whole insight. The other corners share one coordinate with the query point and one with the diagonal.
So: for each candidate diagonal point, check the two remaining corners exist, and multiply the counts.
Why multiply the counts
Duplicate points count separately. If there are 2 copies of one corner, 3 of another and 1 of the third, then there are 2 \times 3 \times 1 = 6 distinct squares.
Multiplying is the combinatorics of choosing one point from each corner independently, and it is why the structure stores counts rather than a set.
Which points to try as the diagonal
Trying every stored point is O(n) per query, which is fine given the constraints — at most 5,000 calls.
The useful narrowing: the diagonal corner must share neither coordinate with the query point and must satisfy the equal-distance condition. Iterating over the counting map's entries and testing each is simple and fast enough.
The solution
python
from collections import defaultdict
class DetectSquares:
def __init__(self):
self.count = defaultdict(int) # (x, y) → how many times added
def add(self, point: List[int]) -> None:
self.count[tuple(point)] += 1
def count(self, point: List[int]) -> int:
x, y = point
total = 0
for (px, py), c in self.count.items():
if abs(px - x) != abs(py - y) or px == x:
continue # not a valid diagonal corner
total += c * self.count[(x, py)] * self.count[(px, y)]
return totalts
class DetectSquares {
private counts = new Map<string, number>();
private key(x: number, y: number): string { return `${x},${y}`; }
add(point: number[]): void {
const k = this.key(point[0], point[1]);
this.counts.set(k, (this.counts.get(k) ?? 0) + 1);
}
count(point: number[]): number {
const [x, y] = point;
let total = 0;
for (const [k, c] of this.counts) {
const [px, py] = k.split(',').map(Number);
if (Math.abs(px - x) !== Math.abs(py - y) || px === x) continue;
total += c
* (this.counts.get(this.key(x, py)) ?? 0)
* (this.counts.get(this.key(px, y)) ?? 0);
}
return total;
}
}px == x must be excluded. If the diagonal shares the query point's x-coordinate, the "square" has zero width — it is a degenerate line, not a square. Checking abs(px - x) != abs(py - y) alone would let px == x and py == y through, since both differences are 0.
defaultdict(int) returns 0 for a missing corner, so a corner that was never added contributes a factor of 0 and the term vanishes. No if needed.
Tuples as dictionary keys work in Python because they are hashable. In JavaScript a Map compares arrays by identity, so the coordinates must be encoded into a string — the same trap as 4.4.4 and 4.20.4.
Only one diagonal needs checking per stored point, because iterating over all stored points naturally visits both diagonals of every square.
Trace
After add([3,10]), add([11,2]), add([3,2]), query (11, 10).
| candidate diagonal | |Δx| vs |Δy| | valid? | other corners | product | |---|---|---|---|---| | (3,10) | 8 vs 0 | no | — | 0 | | (11,2) | 0 vs 8 | no (px == x) | — | 0 | | (3,2) | 8 vs 8 ✓ | yes | (11,2) ×1, (3,10) ×1 | 1 |
Answer 1 ✓ — the square with corners (3,2), (3,10), (11,2), (11,10).
Complexity
add is O(1). count is O(n) for n distinct stored points.
Space is O(n).
A faster variant: index points by x-coordinate, so count only iterates over points sharing the query's y-coordinate — usually far fewer. It adds a second map and is worth mentioning if asked to optimise.
Where this goes next
- Number of Boomerangs (LeetCode 447) — count triples where two distances match, using a map of distance to count. The same "group by a derived key, then combine counts" idea.
- Max Points on a Line — group by the slope from each point, which needs slopes reduced to lowest terms to compare exactly. Never compare slopes as floats; use the reduced fraction
(dy/g, dx/g)as the key. - Valid Square for four given points — check the six pairwise distances: four equal sides and two equal diagonals.
The recurring geometry lesson: compare exact integer quantities, not floating-point ones. Squared distances instead of distances (4.17.3), reduced fractions instead of slopes, and coordinate differences instead of angles.
What the interviewer will push on
"Given two diagonal corners, how do you get the other two?" They swap coordinates: (x, dy) and (dx, y).
"Why multiply the counts?" Duplicates count separately, and you choose one point independently from each corner.
"Why exclude px == x?" A zero-width square is not a square, and the distance test alone lets it through.
"How do you key the points?" Tuples in Python; encoded strings in JavaScript, because arrays compare by identity.
"Could count be faster?" Index by x-coordinate so only relevant points are scanned.
"What about non-axis-aligned squares?" A different and much harder problem — you would rotate coordinates or check all four side vectors for equal length and perpendicularity.
One thing to volunteer: draw the square and read the other two corners off it before writing anything. Geometry problems reward one sketch far more than any amount of algebra.
Next: 4.29 drops to the level of individual bits — the idioms worth memorising, the probabilistic structures Parts 10 and 11 lean on, and what to do when a problem turns out to be NP-hard.