Core Insight Name the mathematical relationship first, then apply it consistently to every position or digit.
Common Pitfall Write down index and boundary conditions before mutating an in-place structure.
Description
Count axis-aligned squares with a given query point.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
arrayhash-tabledesigncounting
Implementation Plan Translate the invariant into these small, testable moves.
- Identify the formula or transformation.
- Set boundary conditions.
- Process each required position.
- Return the transformed result.
class DetectSquares:
def __init__(self):
self.ptsCount = defaultdict(int)
self.pts = []
def add(self, point):
self.ptsCount[tuple(point)] += 1
self.pts.append(point)
def count(self, point):
res = 0
px, py = point
for x, y in self.pts:
if (abs(py - y) != abs(px - x)) or x == px or y == py:
continue
res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
return res