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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Detect Squares

Number: 2139

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Design a data structure to add points on the X-Y plane (where duplicate points are allowed) and, given a query point, count the number of ways to form an axis-aligned square (with positive area) using the query point and three other points in the data structure.

Key Insights

  • Leverage the fact that an axis-aligned square has vertical and horizontal edges.
  • For a query point (x, y), iterate over all points that share the same y-axis. For each of these points (px, y) (with px ≠ x), determine the potential square's side length, d = |px - x|.
  • Check for the existence of the two other points (x, y+d) and (px, y+d) (or (x, y-d) and (px, y-d)) that would complete the square.
  • Use a hash map (or dictionary) to store each point along with its count since duplicate points are allowed.

Space and Time Complexity

Time Complexity:
• The add operation is O(1).
• The count operation is O(n) in the worst-case scenario, where n is the number of distinct points with the same y-coordinate as the query point.

Space Complexity:
• O(m), where m is the number of added points, since we store counts for each point.

Solution

We implement the DetectSquares class by maintaining a hash map (or dictionary) to store the frequency count for each point using its (x, y) coordinates as the key.
In the add(point) method, we simply increment the count for the given point.
For the count(point) method, we iterate through all points that share the same y-coordinate as the query point. For every such point (px, y) (with px ≠ x), we calculate the potential side length of a square (d = px - x). Then, we check for two possible squares: one above the query point and one below it. The count is increased by the number of times these needed points exist multiplied by the count of the current candidate point.
This method efficiently counts all possible squares that can be formed with the query point.

Code Solutions

# Python implementation of DetectSquares
from collections import Counter

class DetectSquares:
    def __init__(self):
        # Use a counter to store the frequency of each point (x, y)
        self.point_counts = Counter()

    def add(self, point):
        x, y = point[0], point[1]
        # Increment the count for the point (x, y)
        self.point_counts[(x, y)] += 1

    def count(self, point):
        x, y = point[0], point[1]
        total_squares = 0
        # Iterate through all points in our data structure
        for (px, py), count in self.point_counts.items():
            # Only consider points that share the same y-coordinate with the query point
            if py == y and px != x:
                # Calculate the potential square's side length
                d = px - x
                # Check for a square above the query point
                total_squares += count * self.point_counts.get((x, y + d), 0) * self.point_counts.get((px, y + d), 0)
                # Check for a square below the query point
                total_squares += count * self.point_counts.get((x, y - d), 0) * self.point_counts.get((px, y - d), 0)
        return total_squares

# Example Usage:
# detectSquares = DetectSquares()
# detectSquares.add([3, 10])
# detectSquares.add([11, 2])
# detectSquares.add([3, 2])
# print(detectSquares.count([11, 10])) # Output: 1
← Back to All Questions