Skip to main content
CodeEasy v0.1

Detect Squares

Medium Subject: Math & Geometry
Time Complexity
O(1) add, O(N) count
Space Complexity
O(N)

Problem Description

Problem Statement

You are given a stream of points on the X-Y plane. Design an algorithm that adds new points and counts the number of squares that can be formed with a specific point as one of the corners.

Example 1:

  • Input: ["DetectSquares", "add", "add", "add", "count", "add", "count"]\n[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]]]
  • Output: [null, null, null, null, 1, null, 2]

Optimal Solution

Python

Approach: Hash Map of Coordinates

Maintain a hash map mapping (x, y) to its frequency. To count squares for a query point (x, y), iterate through all existing points (px, py). If they form a diagonal (absolute differences in x and y are equal and non-zero), find the other two corners (x, py) and (px, y) in the map and multiply their frequencies.

class DetectSquares:
    def __init__(self):
        self.points = defaultdict(int)

    def add(self, point: List[int]) -> None:
        self.points[tuple(point)] += 1

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

        for (px, py), freq in self.points.items():
            if abs(px - x) == abs(py - y) and px != x:
                corner1 = self.points.get((x, py), 0)
                corner2 = self.points.get((px, y), 0)
                res += freq * corner1 * corner2

        return res