⚡Flashcard Drill➔
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

  1. Store the multiplicity of every added point in a hash map keyed by (x, y).
  2. For a query point (x, y), enumerate each stored point (px, py) as a candidate diagonal corner of a square.
  3. 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.
  4. 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 == x or py == 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems