We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Detect Squares

Difficulty: Medium

Problem Description

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 and counts the number of ways to choose three points from the data structure such that the three points and a given query point form an axis-aligned square with positive area.

Key Insights

  • An axis-aligned square can be defined by its diagonal corners.
  • To form a square with a given query point, we need to identify two other points that are equidistant in the x and y directions.
  • Points can be added multiple times, and duplicates are treated as different points.

Space and Time Complexity

Time Complexity: O(1) for adding a point, O(n) for counting squares based on the number of points in the data structure. Space Complexity: O(n) for storing points.

Solution

To solve the problem, we will use a hash table (dictionary) to store the count of each point that is added. The key will be a tuple representing the point (x, y), and the value will be the number of times that point has been added.

When counting squares, given a query point (qx, qy), we will iterate through all points stored in the hash table. For each point (px, py), we can derive the two other points needed to form a square:

  1. (qx, py) - the point that shares the y-coordinate with (px, py).
  2. (px, qy) - the point that shares the x-coordinate with (px, py).

We then check if these derived points exist in the hash table and multiply their counts to get the total combinations for forming squares.

Code Solutions

class DetectSquares:
    def __init__(self):
        self.points = {}  # Dictionary to store point counts

    def add(self, point):
        p = (point[0], point[1])
        if p in self.points:
            self.points[p] += 1  # Increment count if point exists
        else:
            self.points[p] = 1   # Initialize count if point is new

    def count(self, point):
        qx, qy = point
        total_squares = 0
        
        for (px, py), count in self.points.items():
            if abs(px - qx) == abs(py - qy):  # Check for square condition
                total_squares += count * self.points.get((qx, py), 0) * self.points.get((px, qy), 0)

        return total_squares
← Back to All Questions