Skip to content

2013. Detect Squares

  • Time:
    • Constructor: $O(1)$
    • add(point: list[int]): $O(1)$
    • count(point: list[int]): $O(|\texttt{add()}|)$
  • Space: $O(|\texttt{add()}|)$
 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<int> point) {
    ++pointCount[getHash(point[0], point[1])];
  }

  int count(vector<int> point) {
    const int x1 = point[0];
    const int y1 = point[1];
    int ans = 0;

    for (const auto& [hash, count] : pointCount) {
      const int x3 = hash >> 10;
      const int y3 = hash & 1023;
      if (x1 != x3 && abs(x1 - x3) == abs(y1 - y3)) {
        const int p = getHash(x1, y3);
        const int q = getHash(x3, y1);
        if (pointCount.contains(p) && pointCount.contains(q))
          ans += count * pointCount[p] * pointCount[q];
      }
    }

    return ans;
  }

 private:
  unordered_map<int, int> pointCount;

  int getHash(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(getHash(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 hash : pointCount.keySet()) {
      final int count = pointCount.get(hash);
      final int x3 = hash >> 10;
      final int y3 = hash & 1023;
      if (x1 != x3 && Math.abs(x1 - x3) == Math.abs(y1 - y3)) {
        final int p = getHash(x1, y3);
        final int q = getHash(x3, y1);
        if (pointCount.containsKey(p) && pointCount.containsKey(q))
          ans += count * pointCount.get(p) * pointCount.get(q);
      }
    }

    return ans;
  }

  private Map<Integer, Integer> pointCount = new HashMap<>();

  private int getHash(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 = collections.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