Skip to content
AI360Xpert
Back to Math & Geometry
Medium

Detect Squares

You are given a stream of points on an 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 `point = [x, y]` as described above.

Examples

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]
DetectSquares detectSquares = new DetectSquares(); detectSquares.add([3, 10]); detectSquares.add([11, 2]); detectSquares.add([3, 2]); detectSquares.count([11, 10]); // return 1 detectSquares.count([14, 8]); // return 0 detectSquares.add([11, 2]); // duplicate point detectSquares.count([11, 10]); // return 2

Constraints

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

Hash Map (Point Counts)

Approach

We store all points and their frequencies in a Hash Map (or a list since we need to iterate over them). For a given query point `(qx, qy)`, we want to find three other points to form a square. To do this efficiently, we can iterate over all points we've seen so far and treat each point as the *diagonal opposite* of `(qx, qy)`. A point `(x, y)` can form a diagonal with `(qx, qy)` if and only if: 1. It is not the same point (`qx != x` and `qy != y`). 2. The distance along the x-axis equals the distance along the y-axis (`abs(qx - x) == abs(qy - y)`). If it forms a valid diagonal, the other two corners of the square MUST be at `(qx, y)` and `(x, qy)`. The number of ways to form this square is the product of the frequencies of these three points: `freq(x, y) * freq(qx, y) * freq(x, qy)`. We sum this product for all valid diagonal points.

Complexity Analysis

Time Complexity
O(1) for add, O(n) for count
Space Complexity
O(n)

Adding a point takes O(1). Counting takes O(n) where n is the number of points added so far. Space complexity is O(n) to store the points and their frequencies.

Solution.java
class DetectSquares {    private Map<String, Integer> ptsCount;    private List<int[]> pts;
    public DetectSquares() {        ptsCount = new HashMap<>();        pts = new ArrayList<>();    }        public void add(int[] point) {        pts.add(point);        String key = point[0] + "," + point[1];        ptsCount.put(key, ptsCount.getOrDefault(key, 0) + 1);    }        public int count(int[] point) {        int res = 0;        int qx = point[0], qy = point[1];                for (int[] p : pts) {            int x = p[0], y = p[1];                        // Check if it's a valid diagonal (not the same point, and distances are equal)            if (Math.abs(qx - x) != Math.abs(qy - y) || x == qx || y == qy) {                continue;            }                        // The other two points must be (x, qy) and (qx, y)            String p1 = x + "," + qy;            String p2 = qx + "," + y;                        // If both other points exist, add the number of ways to form this square            if (ptsCount.containsKey(p1) && ptsCount.containsKey(p2)) {                res += ptsCount.get(p1) * ptsCount.get(p2);                // Note: we don't multiply by ptsCount.get(x + "," + y) here because                // we are iterating through ALL points in 'pts' individually.                // If there are duplicate diagonal points, the outer loop will visit each one,                // effectively multiplying by its frequency.            }        }                return res;    }}