NeetCode #919LC-2013MediumMath & GeometryNC 150NC 250
← Back to All Problems#919 · #2013 · Detect Squares(检测正方形)
📌 Problem Statement & Constraints
Design a class that stores points on the X-Y plane and answers, for a query point, how many axis-aligned squares can be formed using the query point and three previously added points. Duplicate points are allowed and count separately. Constraints:
1 <= point.length == 2, 0 <= xi, yi <= 1000, at most 5000 calls to add and count.💡 Core Algorithmic Approaches
- Store the multiplicity of every added point in a hash map keyed by
(x, y). - For a query point
(x, y), enumerate each stored point(px, py)as a candidate diagonal corner of a square. - A diagonal corner is valid when
px != x,py != y, and|px - x| == |py - y|-- the two diagonals of an axis-aligned square have equal length and bisect each other. - The two remaining corners are then forced:
(x, py)and(px, y). The number of squares for this diagonal is the product of the three corner multiplicities; sum over all diagonals.
💻 Benchmark Python3 Implementation
class DetectSquares:
def __init__(self):
from collections import defaultdict
self.cnt = defaultdict(int)
def add(self, point: List[int]) -> None:
self.cnt[(point[0], point[1])] += 1
def count(self, point: List[int]) -> int:
x, y = point
total = 0
for (px, py), c in self.cnt.items():
# (px, py) is the diagonal corner opposite to (x, y)
if px != x and py != y and abs(px - x) == abs(py - y):
total += c * self.cnt[(x, py)] * self.cnt[(px, y)]
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) per count, where n is the number of distinct stored points; O(1) per add.
💾 Space Complexity
O(n): one hash-map entry per distinct point.
⚠️ Interview Pitfalls & Follow-ups
- Enumerating the three other corners directly: that is O(n^3); enumerating only the opposite diagonal corner is O(n).
- Forgetting the multiplicity product: duplicate points multiply the number of squares, so each corner count is a factor.
- Allowing
px == xorpy == y: such a point lies on the same horizontal or vertical line and cannot be the opposite corner of a square. - Using a set instead of a counter: duplicates would be collapsed and the answer under-counted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.