2013. Detect Squares

Problem¶

Maintain a multiset of 2D points:

add(point) stores one occurrence.
count(point) returns how many triples of stored occurrences form a positive-area, axis-aligned square with the query point.

Duplicates count separately; the query point need not be stored.

add:   [3, 10], [11, 2], [3, 2]
count: [11, 10] -> 1
add:   [11, 2]
count: [11, 10] -> 2

class DetectSquares:
    def __init__(self):
        pass

    def add(self, point: list[int]) -> None:
        pass

    def count(self, point: list[int]) -> int:
        pass

Key trick¶

Choose a stored point on the query's horizontal line; its distance fixes the square's size, leaving just two possible pairs of corners. Multiply the three stored corners' frequencies.

Trap¶

Exclude zero-width squares, check both vertical directions, and preserve duplicate multiplicities without multiplying by the query point's frequency.

Why is it interesting?¶

Geometry reduces a three-point search to frequency lookups, while duplicates turn counting shapes into counting combinations.

Python solution¶

class DetectSquares:
    def __init__(self):
        # Map each y-coordinate to {x-coordinate: frequency}.
        self.rows = {}

    def add(self, point: list[int]) -> None:
        x, y = point
        row = self.rows.setdefault(y, {})
        row[x] = row.get(x, 0) + 1

    def count(self, point: list[int]) -> int:
        x, y = point
        ans = 0

        for x1, freq in self.rows.get(y, {}).items():
            if x1 == x:
                continue  # Positive area requires distinct horizontal corners.

            width = abs(x1 - x)
            for y1 in (y - width, y + width):
                row = self.rows.get(y1, {})
                # Each occurrence of each stored corner is an independent choice.
                ans += freq * row.get(x, 0) * row.get(x1, 0)

        return ans

Expected time: add takes \(O(1)\); count takes \(O(k)\), where \(k\) is the number of distinct stored points on the query's horizontal line.

Space: \(O(u)\), where \(u\) is the number of distinct stored points.

Comment on my solution¶

Your solution is correct: repeated entries in horizontal[y] implicitly account for the horizontal corner's multiplicity, while the two Counter lookups account for the other corners.

Its query time is \(O(p_y)\), where \(p_y\) includes duplicates on that row, and storage is \(O(a)\) for \(a\) additions. Storing horizontal frequencies instead avoids repeated work and reduces storage to \(O(u)\).

from collections import Counter

# WORKS
class DetectSquares:
    def __init__(self):
        self.freqs = Counter()
        self.horizontal = {}

    def add(self, point: list[int]) -> None:
        x, y = point
        self.freqs[(x,y)] += 1
        self.horizontal.setdefault(y, []).append(x)

    def count(self, point: list[int]) -> int:
        x, y = point
        cnt = 0
        for x1 in self.horizontal.get(y, []):
            if x1 == x:
                continue
            width = abs(x - x1)
            for y1 in (y + width, y - width):
                cnt += self.freqs[(x, y1)] * self.freqs[(x1, y1)]
        return cnt