# 2013. Detect Squares

• Time: Constructor: $O(1)$, add(point: List[int]): $O(1)$, count(point: List[int]): $O(|\texttt{add(point: List[int])}|)$
• Space: $O(|\texttt{add(point: List[int])}|)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class DetectSquares { public: void add(vector point) { ++pointCount[hash(point[0], point[1])]; } int count(vector point) { const int x1 = point[0]; const int y1 = point[1]; int ans = 0; for (const auto& [hashed, count] : pointCount) { const int x3 = hashed >> 10; const int y3 = hashed & 1023; if (x1 != x3 && abs(x1 - x3) == abs(y1 - y3)) { const int p = hash(x1, y3); const int q = hash(x3, y1); if (pointCount.count(p) && pointCount.count(q)) ans += count * pointCount[p] * pointCount[q]; } } return ans; } private: unordered_map pointCount; int hash(int i, int j) { return i << 10 | j; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class DetectSquares { public void add(int[] point) { pointCount.merge(hash(point[0], point[1]), 1, Integer::sum); } public int count(int[] point) { final int x1 = point[0]; final int y1 = point[1]; int ans = 0; for (final int hashed : pointCount.keySet()) { final int count = pointCount.get(hashed); final int x3 = hashed >> 10; final int y3 = hashed & 1023; if (x1 != x3 && Math.abs(x1 - x3) == Math.abs(y1 - y3)) { final int p = hash(x1, y3); final int q = hash(x3, y1); if (pointCount.containsKey(p) && pointCount.containsKey(q)) ans += count * pointCount.get(p) * pointCount.get(q); } } return ans; } private Map pointCount = new HashMap<>(); private int hash(int i, int j) { return i << 10 | j; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class DetectSquares: def __init__(self): self.pointCount = Counter() def add(self, point: List[int]) -> None: self.pointCount[tuple(point)] += 1 def count(self, point: List[int]) -> int: x1, y1 = point ans = 0 for (x3, y3), c in self.pointCount.items(): if x1 != x3 and abs(x1 - x3) == abs(y1 - y3): ans += c * self.pointCount[(x1, y3)] * self.pointCount[(x3, y1)] return ans