Detect Squares LeetCode 2013 Guide

LeetCode 2013 Detect Squares asks you to design a data structure that supports two operations: add(point) which adds a point to the collection (duplicates allowed), and count(point) which returns the number of axis-aligned squares that can be formed using the query point as one corner and three points from the collection as the other three corners.

An axis-aligned square means all four sides are parallel to the x and y axes. Given a query point, you need to efficiently count how many valid squares exist — including counting each distinct combination of three stored points separately, even if multiple copies of those coordinates have been added via repeated add calls.

The problem has constraints that make brute-force infeasible for large inputs: up to 3000 add and count calls, with coordinates in the range [0, 1000]. A naive O(n^3) approach checking all triples of stored points per count call would be too slow. The key insight is that fixing one corner and one diagonal corner uniquely determines the other two corners.

An axis-aligned square has four corners where opposite sides are parallel to the x-axis and y-axis. Given any two diagonally opposite corners (qx, qy) and (px, py), the square is fully determined: the side length equals abs(px - qx), which must equal abs(py - qy) for the corners to be diagonal on a square. The other two corners are (qx, py) and (px, qy).

This geometric fact is the entire algorithm. Rather than iterating over all possible squares or all triples of points, you fix the query point as one corner and enumerate all candidates for the diagonally opposite corner. For each valid diagonal candidate, the remaining two corners are calculated in O(1) — you just check if those corners exist in your data structure and multiply their counts.

The enumeration is efficient because you only need to check stored points that satisfy the diagonal constraint: abs(px - qx) == abs(py - qy) and px != qx. Every such point is a potential diagonal partner, and each one gives exactly one square (or zero, if the other two computed corners are missing from the collection).

Store all added points in a dictionary (or HashMap) keyed by (x, y) tuples, where the value is the count of how many times that point has been added. In Python this is naturally expressed as a defaultdict(int) or Counter. In Java, use a HashMap<String, Integer> or nested HashMap<Integer, HashMap<Integer, Integer>>.

The add operation is O(1): simply increment the count for the key (x, y). Because duplicates are allowed and each duplicate contributes independently to square counts, tracking the frequency is essential. A point added three times effectively exists as three separate points at that location, and the count operation must treat them as such when computing the number of valid squares.

The data structure also benefits from maintaining a separate set of all unique (x, y) coordinates added, or equivalently using the HashMap keys as the set of candidates to iterate over in count. This set grows at most with the number of distinct points added — at most 1001*1001 entries given the coordinate constraints — keeping iteration tractable.

For a query point (qx, qy), iterate over all stored points (px, py). For each point where abs(px - qx) == abs(py - qy) and px != qx (ensuring non-zero side length), treat (px, py) as the diagonally opposite corner. The other two corners are (qx, py) and (px, qy). Look up their counts in the frequency map — if either is zero, no square exists for this diagonal.

Multiply the counts of all three non-query corners: pointCount[(px, py)] * pointCount[(qx, py)] * pointCount[(px, qy)]. Add this product to the running total. The multiplication correctly handles duplicates: each copy of the diagonal and each copy of the two side corners independently contribute to valid squares, so the number of squares from this diagonal choice is exactly the product of the three frequencies.

The total count is the sum of these products over all valid diagonal points. Because we iterate over all stored points once per count call, the time complexity is O(n) per count where n is the number of distinct stored points. With at most 3000 add calls, n <= 3000 in the worst case, making each count call fast enough.

A straightforward optimization reduces the constant factor: instead of iterating all stored points and checking the diagonal constraint, maintain a secondary mapping from x-coordinate to the set of y-values at that x. Then for count(qx, qy), iterate only over points sharing the same x-coordinate as a stored point — but a different x — to find potential same-row partners, then compute the implied diagonal.

Alternatively, maintain a mapping from y-coordinate to set of x-values. For each point (px, py) with the same y as the query (py == qy), compute the implied side length s = abs(px - qx). Check if (px, qy + s) and (qx, qy + s) exist, and also if (px, qy - s) and (qx, qy - s) exist. This approach enumerates candidates along the same horizontal row as the query, with two square directions (above and below).

Both approaches are O(n) per count in the worst case, but the row-based approach avoids iterating points that fail the diagonal constraint immediately. For inputs with many distinct x or y values, the savings are modest. The simpler all-points approach with the abs check is clear and correct; the row-based approach is a constant-factor optimization worth knowing for interview discussions.

Python solution: from collections import defaultdict; class DetectSquares: def __init__(self): self.ptCount = defaultdict(int); self.pts = set(); def add(self, point): self.ptCount[tuple(point)] += 1; self.pts.add(tuple(point)); def count(self, point): qx, qy = point; res = 0; for px, py in self.pts: if abs(px - qx) != abs(py - qy) or px == qx: continue; res += self.ptCount[(px, py)] * self.ptCount[(qx, py)] * self.ptCount[(px, qy)]; return res. The pts set avoids re-iterating duplicate coordinates during count.

Java solution: class DetectSquares { Map<String, Integer> ptCount = new HashMap<>(); Set<String> pts = new HashSet<>(); private String key(int x, int y) { return x + "," + y; } public void add(int[] p) { String k = key(p[0], p[1]); ptCount.merge(k, 1, Integer::sum); pts.add(k); } public int count(int[] point) { int qx = point[0], qy = point[1], res = 0; for (String pk : pts) { String[] parts = pk.split(","); int px = Integer.parseInt(parts[0]), py = Integer.parseInt(parts[1]); if (Math.abs(px-qx) != Math.abs(py-qy) || px == qx) continue; res += ptCount.get(pk) * ptCount.getOrDefault(key(qx,py),0) * ptCount.getOrDefault(key(px,qy),0); } return res; } }

Time complexity: add is O(1). count is O(n) where n is the number of distinct stored points. Space complexity: O(n) for the frequency map and point set. Both Python and Java solutions correctly handle all edge cases including duplicate points and queries with no valid squares.

Valid Sudoku (LeetCode 36) uses HashSets to track digit presence per row, column, and box — a similar pattern of multi-key lookups to validate constraints on a 2D grid. Two Sum (LeetCode 1) is the canonical HashMap frequency pattern: store seen values and query complement existence in O(1). Both problems share the same fundamental idea as Detect Squares: use a map to make membership queries O(1) instead of O(n).

Insert Delete GetRandom O(1) (LeetCode 380) combines a HashMap with an array to achieve uniform random sampling — another design problem where the data structure choice drives all operations to O(1) expected. The coordinate geometry family also includes Max Points on a Line (LeetCode 149), where you count points sharing a slope from each anchor, and Number of Boomerangs (LeetCode 447), which counts point triplets with equal distances using a frequency map per anchor point.

Detect Squares sits at the intersection of geometry and HashMap design: the geometry determines which corners to check, while the HashMap enables O(1) frequency lookups that make the overall algorithm efficient. Practicing this family builds intuition for when a frequency map reduces an apparent O(n^k) combinatorial problem to O(n) or O(n^2) by exploiting geometric or algebraic structure to eliminate redundant enumeration.