Why try each stored point as the diagonal corner?

An axis-aligned square is fixed by two diagonal corners. The query point is one; once you pick the opposite corner p, the other two corners must be (p.x, q.y) and (q.x, p.y). So checking every stored point as p, and looking up the two implied corners, finds every square without ever searching for them.

Why multiply the counts?

Points can be added more than once, and each copy counts as a different point. If p was added 2 times, (p.x, q.y) once and (q.x, p.y) 2 times, there are 2 × 1 × 2 = 4 different ways to pick one copy of each corner, so 4 squares.

Why skip points in the same column?

What does count() cost?

One pass over the distinct stored points, O(p), with O(1) hash lookups for the two other corners. add() is O(1). An alternative scans only the points in the query's column and checks both sides, which is faster when columns are short; both are accepted.

Detect Squares

Count the axis-aligned squares a query point can complete with stored points: a hash map of point counts, and each stored point tried as the diagonal corner.

MediumSolve on LeetCode

Problem Understanding

Detect Squares: design a structure with add(point), which stores a point (duplicates allowed), and count(point), which returns how many ways the query point and three stored points can form an axis-aligned square with positive area.

Example: after add([3,10]), add([11,2]), add([3,2]), count([11,10]) returns 1; after another add([11,2]), it returns 2.

The Intuition: The Diagonal Fixes the Square

Two diagonal corners decide an axis-aligned square completely:

Store counts, not lists. A hash map from point to the number of times it was added handles duplicates for free.
Try each stored point as the opposite corner. It qualifies only if it is as far across as it is up or down, and not in the same column.
The other two corners are forced, so look them up and multiply all three counts.

It is the same counting idea as Two Sum: instead of searching for the partner, compute exactly what the partner must be and look it up. Valid Sudoku is another grid problem solved by hashing coordinates.

Interactive Walkthrough

CELL = TIMES ADDED · ONLY USED ROWS AND COLUMNS

EMPTY COUNTER

call

total

returns

Start with an empty counter: point → how many times it was added

add(3, 10): cnt[(3, 10)] = 1

Free preview: the first 6 of 20 steps

calls

Each cell shows how many times that point was added; only the x and y values the calls use are drawn, so corners still line up. During count, the query point is solid; each stored point is tried in turn, struck out if it is not a diagonal, or tinted with the two corners it implies. Try Duplicates to see the counts multiply.

Dry Run Table

Calls: add(3,10), add(11,2), add(3,2), then count(11,10).

Stored point p	Diagonal?	Corners (p.x, q.y), (q.x, p.y)	Adds
(3,10)	no: 8 across, 0 up	-	0
(11,2)	no: same column	-	0
(3,2)	yes: 8 and 8	(3,10) ×1, (11,2) ×1	1 · 1 · 1 = 1

Answer: 1. After a second add(11,2), the same scan gives 1 · 1 · 2 = 2.

The Solution Template

A counter keyed by point; count scans the distinct points and multiplies the three corner counts.

Detect Squares Code

1var DetectSquares = function() {
2    this.cnt = new Map();
3};
4
5DetectSquares.prototype.add = function(point) {
6    const k = point.join(',');
7    this.cnt.set(k, (this.cnt.get(k) || 0) + 1);
8};
9
10DetectSquares.prototype.count = function(point) {
11    const [qx, qy] = point;
12    let total = 0;
13    for (const [k, c] of this.cnt) {
14        const [px, py] = k.split(',').map(Number);
15        if (Math.abs(px - qx) !== Math.abs(py - qy) || px === qx) continue;
16        total += c * (this.cnt.get(`${px},${qy}`) || 0) * (this.cnt.get(`${qx},${py}`) || 0);
17    }
18    return total;
19};

Edge Cases & Common Mistakes

Zero-area squares: skip points in the query's column (or row); the problem wants positive area.
Adding 1 instead of multiplying: duplicates make several distinct squares; multiply the three counts.
Inserting while looking up: in Python, self.cnt[(px, qy)] on a defaultdict inserts a key while you iterate; use .get (or iterate over a copy).
The query point is not stored: count must not add it; only add changes the counter.
Squares on both sides: a query can complete squares to the left and right, above and below; trying every stored diagonal covers all four directions.

Summary

Keep a hash map of point counts. For count(q), try every stored point p with |p.x − q.x| = |p.y − q.y| and p.x ≠ q.x as the opposite corner, and add cnt[p] · cnt[(p.x, q.y)] · cnt[(q.x, p.y)]. add is O(1); count is O(p) over distinct points.

More practice: DSA interview questions with answers · patterns cheat sheet

Valid Sudoku

Majority Element