← DSA Atlas
Dedicated problem page · #2013

Detect Squares

MediumArrays and HashingDiagonal enumeration over a point-frequency mapHash map counting points by coordinate
Solve on LeetCode ↗
2013
MediumArrays and HashingHash map counting points by coordinateDiagonal enumeration over a point-frequency map

Detect Squares

Design a data structure DetectSquares that streams in 2D points. add([x, y]) inserts a point (duplicates allowed). count([x, y]) returns the number of ways to pick three points already added that, together with the query point, form an axis-aligned square with positive area. Points chosen may repeat if they were added multiple times, and counts multiply accordingly.

Open official problem prompt ↗
In plain English

Answer, on demand, how many axis-aligned squares of positive area a query point can form with three previously added points.

Picture it like this

Picture a pegboard where you keep tallies of how many pegs sit at each hole. To count squares through a chosen hole, you look for pegs sitting on a perfect 45-degree diagonal from it; each such peg fixes the opposite two holes, and you multiply how many pegs occupy all three.

Example
Input
add([3,10]); add([11,2]); add([3,2]); count([11,10])
Output
1
Why
The query (11,10) with the diagonal point (3,2) needs corners (11,2) and (3,10); all three exist once, forming exactly one axis-aligned square of side 8.
Constraints
point[0], point[1] in [0, 1000]At most 3000 total calls to add and countA valid square must have positive area (side length > 0)
Pattern lesson

See the pattern, then code

Diagonal enumeration over a point-frequency map
Recognition clue

A design problem that repeatedly queries for squares over a growing point set, with a tiny coordinate range and few calls, signals storing point frequencies in a hash map and enumerating candidate diagonals per query rather than any geometric sweep.

↗
Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Fix the query point as one corner. Any other stored point on a true diagonal (equal horizontal and vertical distance, and not sharing the query's column) determines the whole square; the two remaining corners are forced, so multiply the three frequencies.

New words, made simpleKnow these before the algorithm
Axis-aligned square
A square whose sides are parallel to the x and y axes, so its four corners share x and y coordinates pairwise.
Diagonal corner
The corner opposite the query point; for an axis-aligned square it satisfies |dx| == |dy| with dx != 0.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate all triples per query

Cubic per query; hopelessly slow even for a few thousand points.

For each count, try every combination of three stored points.

Time O(m^3) per querySpace O(m)
Best choiceFrequency map + diagonal scan

Linear per query with O(1) add; fits the call limits comfortably.

Store point counts; per query, scan candidate diagonal points and multiply the three corner frequencies.

Time O(m) per querySpace O(m)
The rule we keep true

Invariant

self.cnt[(x, y)] always equals the number of times point (x, y) has been added so far.

Why this is correct

Reasoning

An axis-aligned square is uniquely determined by the query corner and its diagonally opposite corner: given (qx,qy) and a diagonal (px,py) with equal horizontal and vertical offset, the other two corners must be (qx,py) and (px,qy). The px != qx guard enforces positive area (nonzero side). Multiplying the three stored frequencies counts every distinct combination of added points, and summing over all valid diagonals covers every square exactly once (each square has exactly one corner diagonally opposite the query).

The algorithm in three movesSay these aloud before coding
1Maintain a Counter mapping (x, y) to how many times it was added

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

2add: increment the counter for the given point

query (11,10): diagonal (3,2) valid

3count: for each stored point (px, py) with |px-qx| == |py-qy| and px != qx, it is a diagonal corner

1 * cnt[(11,2)] * cnt[(3,10)] = 1

4Add count[(px,py)] * count[(qx,py)] * count[(px,qy)] for each such diagonal and return the total

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(3,10)0
(11,2)1
(3,2)2
(11,10)?3
1 · Read[3,10]
2 · Ask-
3 · Update statecnt={(3,10):1}
4 · Resultstored
Key takeaway

Query corner (11,10) pairs with diagonal (3,2); the forced corners (11,2) and (3,10) complete the square.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 7-8add

    Bump the frequency of the exact coordinate; duplicates accumulate so combinations multiply later.

  2. 2
    Lines 10-16count

    Scan every stored point; keep only true diagonals (equal offsets, nonzero side), then multiply the frequencies of the diagonal and the two forced corners.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No square possible -> return 0
  • Duplicate points added, so a corner frequency exceeds 1 and squares multiply
  • Query point coincides with stored points (still valid as long as the diagonal has positive side)
  • Points sharing a row or column with the query but not on a diagonal, which the |dx|==|dy| test rejects
!

Common beginner mistakes

  • Naming the attribute the same as the method count, which shadows one of them; store frequencies under a distinct name like cnt
  • Omitting the px != qx (positive-area) check, which counts degenerate zero-side 'squares'
  • Adding instead of multiplying the three corner frequencies, ignoring duplicate points
  • Forgetting that a point can be its own query and mishandling the missing corners' zero counts (Counter returns 0, which is correct)
Check your understanding

Given the query corner and one diagonal corner, why are the other two corners fully determined?

More in Arrays and Hashing

#1Two SumComplement lookup#49Group AnagramsCanonical key bucketing#238Product of Array Except SelfPrefix and suffix products#128Longest Consecutive SequenceSequence-start expansion#560Subarray Sum Equals KPrefix-sum complement count#36Valid SudokuConstraint tracking with sets