Detect Squares

Store every added point in a plain list, duplicates included. To answer a query, scan the list for any point sharing the query’s x-coordinate (a potential vertical side partner), compute the required side length, and use list.count(...) to check how many copies of the two remaining corners exist — a linear scan for each of those lookups makes each candidate check O(n).

class DetectSquares:
    def __init__(self):
        self.points = []

    def add(self, point: list[int]) -> None:
        self.points.append(tuple(point))

    def count(self, point: list[int]) -> int:
        px, py = point
        total = 0
        for x, y in self.points:
            if x != px or y == py:
                continue
            side = y - py
            for dx in (side, -side):
                total += self.points.count((px + dx, py)) * self.points.count((px + dx, y))
        return total

Complexity: add just appends → O(1). count scans all n stored points, and for each candidate partner does two O(n) .count() lookups → O(n²) time. Storage is one entry per point → O(n) space.

Keep the exact same geometric idea, but replace the slow list scans with two hash maps: one mapping every (x, y) pair to how many times it has been added, and one mapping each x-coordinate to a {y: count} dictionary of the points in that column. This turns “how many points share the query’s column” and “does this exact point exist” from O(n) scans into O(1) lookups, and means the outer loop only visits distinct y-values in the query’s column instead of every duplicate.

from collections import defaultdict

class DetectSquares:
    def __init__(self):
        self.point_count = defaultdict(int)
        self.cols = defaultdict(lambda: defaultdict(int))  # x -> {y: count}

    def add(self, point: list[int]) -> None:
        x, y = point
        self.point_count[(x, y)] += 1
        self.cols[x][y] += 1

    def count(self, point: list[int]) -> int:
        px, py = point
        total = 0
        for y, freq in self.cols[px].items():
            if y == py:
                continue
            side = y - py
            total += freq * self.point_count[(px + side, py)] * self.point_count[(px + side, y)]
            total += freq * self.point_count[(px - side, py)] * self.point_count[(px - side, y)]
        return total

Watch a count query pick its vertical partner and test the one or two squares that side implies:

Tracing the example: after add([3,10]), add([11,2]), add([3,2]), calling count([11,10]) looks at column 11, finds y=2 with freq=1. The signed side offset is 2 - 10 = -8, placing the square 8 units to the left. Checking (11-8, 10) = (3,10) (present, count 1) and (11-8, 2) = (3,2) (present, count 1) gives 1 * 1 * 1 = 1; checking the other direction, (19,10) and (19,2), are both absent, contributing 0. Total: 1, matching the expected output. After add([11,2]) again, freq for y=2 in column 11 becomes 2, so the same square is now counted twice — matching the expected 2.

Complexity: add does O(1) dictionary updates. count iterates over the distinct y-values sharing the query’s column — at most n in the worst case, each doing O(1) hash lookups → O(n) time. Both maps together hold O(n) space.