DSAPrep
MediumMath & Geometry

Detect Squares

You are given a stream of points on the X-Y plane. Design an algorithm that:

Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points.

Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area.

An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis.

Implement the DetectSquares class: DetectSquares() initializes the object with an empty data structure. void add(int[] point) adds a new point point = [x, y] to the data structure. int count(int[] point) counts the number of ways to form axis-aligned squares with point = [x, y] as described above.

Example 1

Input: ["DetectSquares", "add", "add", "add", "count", "count", "add", "count"], [[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
Output: [null, null, null, null, 1, 0, null, 2]
Explanation: After adding (3,10), (11,2), (3,2): count([11,10]) finds one square using those three points. count([14,8]) finds none. After adding a duplicate (11,2), count([11,10]) now finds 2 squares (one using each copy of (11,2)).

Constraints

  • point.length == 2
  • 0 <= x, y <= 1000
  • At most 3000 calls in total will be made to add and count.
View original on LeetCode ↗

For the query point (px, py) to be one corner of an axis-aligned square, there must be a stored point directly above or below it — sharing the same x-coordinate — since that’s the only way to form a vertical side. If such a point (px, y) exists, the side length is |y - py|, which immediately tells you where the other two corners of the square must be: (px + side, py) and (px + side, y) (or px - side for the square on the other side). The whole problem reduces to checking whether those two exact points are present, and multiplying together how many copies of each of the three partner points exist (since duplicates create independent squares).

Brute Force with Linear Scans

Time O(1) add, O(n²) countSpace O(n)

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.

Hash Maps Grouped by Column

OptimalTime O(1) add, O(n) countSpace O(n)

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

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. Side length is 2 - 10 = -8. 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.