Restating the Problem: You are designing a system that receives a stream of 2D coordinates (points). At any given time, the system can be asked a query: "Given a target point, how many distinct axis-aligned squares can be formed using this target point and any three points we've previously recorded?"
Constraints to note: Up to 5000 calls will be made in total. Duplicate points are allowed and must be treated as distinct items.
Edge cases: A square must have a positive, non-zero area (lines don't count).
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.
The naive approach for count would be to iterate through every possible combination of 3 points from our stored list and check if they, together with the query point, form a square. If we have n points, checking all triplets takes O(n^3) time per query. With up to 5000 calls, n^3 is roughly 125 billion operations, easily resulting in TLE. We need a way to deduce the other points instead of searching for them.
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:
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.
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.
(1) How many times each point has been added. The same point can be added more than once, and each copy counts as a separate corner. The attribute is called counts, not count, on purpose. A Python object's attributes and methods share one set of names. An attribute called count would hide the count method, and calling it would crash.
(2) Adding a point adds one to its tally.tuple(point) turns the list [x, y] into (x, y), because a list cannot be a dictionary key in Python.
(3) Try every stored point as the corner diagonally opposite the query point.
(4) It can only be the opposite corner of a square if it is the same distance away across as it is up or down, and not on the same vertical line. The distance across is abs(px - x) and the distance up or down is abs(py - y). If those differ, the shape would be a rectangle that is not square. If px == x, the "square" would have no width.
(5) Count the squares that use this diagonal. The other two corners must be at (x, py) and (px, y). Every copy of each corner gives a different square, so multiply the three counts together. We use .get(..., 0) rather than [...] for a reason. Looking up a missing key in a defaultdict with [...]adds that key. Adding keys to a dictionary while looping over it stops Python with an error.
(6) The total number of squares.
Code Walkthrough:
Initialization: We use a defaultdict(int) to map each point (x, y) to its frequency.
Adding Points: In add, we just increment the count for the tuple (x, y).
Counting Squares (count): We extract x and y from the query. We iterate through every unique point (px, py) in our hash map, treating it as the diagonal opposite corner.
Validation: We check if it forms a square by verifying the horizontal and vertical distances are equal (abs(px - x) == abs(py - y)). We also ensure it's not a zero-width square (px != x). If it fails, we continue.
Combinatorics: If it's a valid diagonal, the two missing corners must be (x, py) and (px, y). We multiply the frequencies of all three points (the diagonal and the two missing corners) and add this product to our 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.
add is O(1). count is O(n) for n distinct stored points.
Space is O(n).
Time Complexity:
add: O(1). Hash map insertion/increment is constant time.
count: O(n) where n is the number of unique points added so far. We loop over the hash map keys once per query.
Space Complexity:O(n) to store up to n unique points in the hash map.
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.
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.
"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.28.9 collects the number theory these problems keep brushing against: Euclid's gcd, the sieve of primes, and arithmetic modulo 10⁹ + 7, with the traps that break correct-looking solutions.