{x}
blog image

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 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
DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // return 1. You can choose:
                               //   - The first, second, and third points
detectSquares.count([14, 8]);  // return 0. The query point cannot form a square with any points in the data structure.
detectSquares.add([11, 2]);    // Adding duplicate points is allowed.
detectSquares.count([11, 10]); // return 2. You can choose:
                               //   - The first, second, and third points
                               //   - The first, third, and fourth points

 

Constraints:

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

Solution: Detect Squares

This problem requires designing a data structure to efficiently add points and count the number of axis-aligned squares formed with a given query point. A hash table (or dictionary in Python) provides an effective solution.

Approach:

  1. Data Structure: We use a nested hash table (or dictionary) cnt. The outer hash table keys are x-coordinates, and the inner hash tables store y-coordinates as keys and their counts as values. This allows for O(1) lookup of point counts.

  2. add(point): This method simply increments the count of the given point (x, y) in the cnt data structure.

  3. count(point): This is the core logic. Given a query point (x1, y1), we need to find three other points to form a square. We iterate through all existing x-coordinates (x2). For each x2, we calculate the side length d = abs(x2 - x1). If d > 0, we check for the existence of points (x1, y1 + d), (x2, y1 + d), (x1, y1 - d), and (x2, y1 - d). If all these points exist, we add their counts to the total square count. This approach efficiently identifies all possible squares.

Time Complexity Analysis:

  • add(point): O(1) - Constant time to update the count in the hash table.
  • count(point): O(n*m), where 'n' is the number of unique x-coordinates and 'm' is the maximum number of unique y-coordinates associated with any single x-coordinate. In the worst case, it might iterate through all points to check for square formations. However, on average, performance is better as it will often find fewer than 'n' potential squares to check.

Space Complexity Analysis: O(N), where N is the total number of points added. This is because we store all the points in the cnt hash table.

Code Implementation (Python):

from collections import defaultdict, Counter
 
class DetectSquares:
    def __init__(self):
        self.cnt = defaultdict(Counter)  # Nested dictionary for efficient point counting
 
    def add(self, point: List[int]) -> None:
        x, y = point
        self.cnt[x][y] += 1
 
    def count(self, point: List[int]) -> int:
        x1, y1 = point
        if x1 not in self.cnt:
            return 0  # No points with this x-coordinate
 
        ans = 0
        for x2, y_counts in self.cnt.items(): #Iterate through existing x-coordinates
            if x2 != x1:
                d = abs(x2 - x1)
                if y1 + d in y_counts and y1 - d in y_counts and y1 in y_counts:
                    ans += y_counts[y1] * y_counts[y1 + d] * self.cnt[x2][y1 + d]
                    ans += y_counts[y1] * y_counts[y1 - d] * self.cnt[x2][y1 - d]
        return ans

Code Implementation (Java):

import java.util.HashMap;
import java.util.Map;
 
class DetectSquares {
    private Map<Integer, Map<Integer, Integer>> cnt = new HashMap<>();
 
    public DetectSquares() {}
 
    public void add(int[] point) {
        int x = point[0], y = point[1];
        cnt.computeIfAbsent(x, k -> new HashMap<>()).merge(y, 1, Integer::sum);
    }
 
    public int count(int[] point) {
        int x1 = point[0], y1 = point[1];
        if (!cnt.containsKey(x1)) return 0;
 
        int ans = 0;
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : cnt.entrySet()) {
            int x2 = entry.getKey();
            if (x2 != x1) {
                int d = Math.abs(x2 - x1);
                Map<Integer, Integer> yCounts1 = cnt.get(x1);
                Map<Integer, Integer> yCounts2 = entry.getValue();
                if (yCounts1.containsKey(y1 + d) && yCounts1.containsKey(y1 - d) && yCounts2.containsKey(y1)) {
                    ans += yCounts2.get(y1) * yCounts1.get(y1 + d) * yCounts2.get(y1 + d);
                    ans += yCounts2.get(y1) * yCounts1.get(y1 - d) * yCounts2.get(y1 - d);
                }
            }
        }
        return ans;
    }
}

Similar implementations can be created in other languages like C++, Go, Javascript etc., following the same logic and data structure. The key is the efficient use of a hash table to store and access point counts.