Count the axis-aligned squares a query point makes with stored points. Keep point counts in a hash map and scan for diagonal corners.
▼The problem
LeetCode 2013 (Medium). Design a class DetectSquares: add(point) stores a point on the plane (duplicates allowed, each copy counts separately) and count(point) returns the number of ways to choose three stored points that form an axis-aligned square of positive area together with the query point.
Example (LeetCode's): add [3,10], add [11,2], add [3,2], count [11,10] → 1, count [14,8] → 0, add [11,2], count [11,10] → 2.
The solution
from collections import Counter
class DetectSquares:
def __init__(self):
self.cnt = Counter() # point -> copies
def add(self, point):
self.cnt[tuple(point)] += 1
def count(self, point):
x, y = point
ways = 0
for (px, py), n in self.cnt.items():
if abs(px - x) != abs(py - y) or px == x:
continue # off the diagonal
ways += n * self.cnt[(x, py)] * self.cnt[(px, y)]
return waysTranscript
Detect Squares. Design a class with two moves. Add stores a point, and duplicates are allowed. Count takes a query point: in how many ways can three stored points form a square with it? Its sides are axis-aligned, with positive area.
Add three ten, eleven two, and three two. Count eleven ten: those three close one square: the answer is one. Count fourteen eight: zero. Add eleven two again, and count eleven ten: now two ways, one for each copy.
The easy way tries every triple of stored points for each query. With n points, that's order n cubed per count.
The trick: a hash map from each point to its count. Picture each point as a float on a pond, with copies stacked up. A square is fixed by the query and its opposite corner, so scan for that diagonal float: its x and y distances must match, and not be zero. Then the other two corners are known. Multiply the three counts.
In code, add bumps a count. Count loops over the map, skips anything off the diagonal, and adds the product of the three counts.
Count eleven ten. Three ten and eleven two share its row or column, so they're skipped. Three two is eight across and eight down: a diagonal. Its other corners, eleven two and three ten, hold two and one. One times two times one: two squares.
Add is order one. Count is order n over the distinct points, and the map uses order n space.
Store, find the diagonal, multiply. That's Detect Squares.