Detect Squares
Problem
Implement a data structure that supports adding points on a 2D plane and counting the number of axis-aligned squares that can be formed with a given query point as one of the vertices.
- point.length == 2
- 0 ≤ point[i] ≤ 1000
- At most 5000 calls will be made to add and count
Example
add([3, 10]), add([11, 2]), add([3, 2]), count([11, 10])1After adding points (3,10), (11,2), and (3,2), the query count([11,10]) asks how many squares can be formed with (11,10) as one vertex. The square with vertices (11,10), (3,10), (3,2), and (11,2) exists. The algorithm identifies points sharing the same x-coordinate as the query point (3,10) and calculates the side length. It then checks for the other two vertices (11,10) and (11,2) in the stored points. The count is incremented by the product of the occurrences of these points, resulting in 1.
Approach
Straightforward Solution
A brute-force approach would check all triplets of points to see if they form a square with the query point, resulting in O(n^3) time complexity, which is infeasible for large inputs.
Core Observation
Squares aligned with the axes have equal side lengths and share either the same x or y coordinate for pairs of vertices. For a query point, potential squares can be found by identifying points sharing the same x-coordinate but different y-coordinates, then checking for the corresponding points that complete the square horizontally.
Path to Optimal
The key insight is to store points in a hash map keyed by their coordinates with counts of occurrences. For a query point, iterate over points with the same x-coordinate but different y-coordinates to determine possible side lengths. For each side length, check if the two other points that would complete the square exist in the map. Multiplying their counts with the count of the vertical point gives the number of squares formed. This reduces the problem to O(k) per query, where k is the number of points sharing the x-coordinate.
Optimal Approach
Use a hash map to store counts of all added points. For counting, extract all points with the same x-coordinate as the query point but different y-coordinates. For each, compute the side length and check for the existence of the two points that would complete the square on both sides horizontally. Sum the products of their counts to get the total number of squares. This approach leverages O(1) average lookup and efficient iteration over relevant points.
Time
O(k) per count query, where k is the number of points sharing the query point's x-coordinate
Each count query iterates over points with the same x-coordinate as the query point, performing constant-time hash map lookups for the complementary points. Adding points is O(1) amortized due to hash map insertion.
Space
O(n)
The hash map stores counts for all added points, which can be up to n in the worst case, where n is the number of add operations.
Pattern Spotlight
Hash Maps (Frequency Counting with Coordinate Grouping)
When counting geometric shapes formed by points, group points by one coordinate and use hash maps to quickly find complementary points that complete the shape, multiplying counts to account for duplicates.
Solution
| 1 | import collections
|
| 2 |
|
| 3 | class DetectSquares:
|
| 4 | def __init__(self):
|
| 5 | self.pts_count = collections.defaultdict(int)
|
| 6 |
|
| 7 | def add(self, point: list[int]) -> None:
|
| 8 | self.pts_count[tuple(point)] += 1
|
| 9 |
|
| 10 | def count(self, point: list[int]) -> int:
|
| 11 | res = 0
|
| 12 | px, py = point
|
| 13 |
|
| 14 | y_points = [y for x_val, y in self.pts_count if x_val == px and y != py]
|
| 15 |
|
| 16 | for y2 in y_points:
|
| 17 | side = py - y2
|
| 18 |
|
| 19 | p3 = (px + side, py)
|
| 20 | p4 = (px + side, y2)
|
| 21 | if p3 in self.pts_count and p4 in self.pts_count:
|
| 22 | res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]
|
| 23 |
|
| 24 | p3 = (px - side, py)
|
| 25 | p4 = (px - side, y2)
|
| 26 | if p3 in self.pts_count and p4 in self.pts_count:
|
| 27 | res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]
|
| 28 | return res // 2 |
Step-by-Step Solution
Store Points with Frequency Counts Using a Hash Map
| 5 | self.pts_count = collections.defaultdict(int)
|
| 8 | self.pts_count[tuple(point)] += 1
|
Objective
To record each added point and its frequency for quick lookup during square counting.
Key Insight
Storing points as keys in a hash map with their counts allows constant-time retrieval of how many times a point has been added. This frequency information is crucial because multiple identical points can form multiple squares, and the count must reflect all occurrences. Using a tuple as the key ensures hashability and efficient access.
Interview Quick-Check
Core Logic
Use a hash map keyed by point coordinates to store counts, enabling O(1) average-time insertion and lookup.
Common Pitfalls & Bugs
Failing to count multiple occurrences of the same point leads to incorrect square counts.
Identify Candidate Vertical Points Sharing Query X-Coordinate
| 14 | y_points = [y for x_val, y in self.pts_count if x_val == px and y != py]
|
Objective
To find all points that share the same x-coordinate as the query point but have different y-coordinates, representing potential vertical edges of squares.
Key Insight
Squares aligned with the axes have vertical sides with constant x. By filtering points to those with the same x but different y, the algorithm narrows down the search space to only relevant candidates that can form vertical sides with the query point. This reduces unnecessary checks and leverages the geometric property of squares.
Interview Quick-Check
Core Logic
Filter points by matching x-coordinate and differing y-coordinate to identify vertical edges of potential squares.
Complexity
This filtering limits iteration to only points that can form vertical sides, improving efficiency over scanning all points.
Calculate Side Lengths and Check for Complementary Points to Complete Squares
| 16 | for y2 in y_points:
|
| 17 | side = py - y2
|
| 19 | p3 = (px + side, py)
|
| 20 | p4 = (px + side, y2)
|
| 21 | if p3 in self.pts_count and p4 in self.pts_count:
|
| 22 | res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]
|
| 24 | p3 = (px - side, py)
|
| 25 | p4 = (px - side, y2)
|
| 26 | if p3 in self.pts_count and p4 in self.pts_count:
|
| 27 | res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]
|
Objective
To compute the side length of potential squares and verify the existence of the other two vertices that complete the square on both horizontal sides.
Key Insight
For each candidate vertical point, the side length is the vertical distance from the query point. The other two points that complete the square lie horizontally at a distance equal to the side length from the query point and the candidate point. Checking both directions (left and right) ensures all possible squares are counted. Multiplying the counts of these points accounts for multiple occurrences, correctly tallying all squares.
Interview Quick-Check
Core Logic
For each vertical candidate, compute side length and check existence of the two horizontal points on both sides to count all squares.
State & Boundaries
Consider both positive and negative side lengths to cover squares on both sides of the vertical line.
Common Pitfalls & Bugs
Forgetting to multiply counts of all three points leads to undercounting squares formed by duplicate points.
Return Half the Accumulated Count to Correct Double Counting
| 11 | res = 0
|
| 28 | return res // 2 |
Objective
To adjust the final count by dividing by two, correcting for double counting of squares due to symmetric checks.
Key Insight
Each square is counted twice because the algorithm checks both left and right horizontal completions independently. Dividing the accumulated count by two removes this duplication, ensuring the returned count accurately reflects the number of unique squares.
Interview Quick-Check
Core Logic
Divide the total count by two to correct for double counting caused by symmetric checks on both sides.
Common Pitfalls & Bugs
Omitting this division results in counting each square twice, leading to incorrect results.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
return res // 2Return half the accumulated count to correct for double counting.
Each square is counted twice (once from each horizontal direction), so dividing by two yields the correct unique count.
self.pts_count[tuple(point)] += 1Increment the count for the added point in the hash map.
This line updates the frequency of the point, which is essential for correctly counting squares that involve multiple identical points.
if p3 in self.pts_count and p4 in self.pts_count:Check if both right-side horizontal points exist in the stored points.
Verifying the existence of these points confirms the presence of a complete square on the right side.
res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]Increment the result by the product of counts of the three points forming the right-side square.
Multiplying counts accounts for multiple occurrences of each point, ensuring all distinct squares formed by duplicates are counted.
if p3 in self.pts_count and p4 in self.pts_count:Check if both left-side horizontal points exist in the stored points.
Ensures the left-side square is valid by confirming the presence of required points.
res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]Increment the result by the product of counts of the three points forming the left-side square.
Accounts for all squares formed on the left side, including duplicates, by multiplying counts.
self.pts_count = collections.defaultdict(int)Initialize a default dictionary to count occurrences of points.
Using a defaultdict with int default allows efficient counting of points without explicit existence checks, enabling O(1) amortized insertion and lookup.
y_points = [y for x_val, y in self.pts_count if x_val == px and y != py]Collect all y-coordinates of points sharing the query point's x-coordinate but different y.
Filtering points by x-coordinate reduces the search space to only those that can form vertical sides of squares with the query point, leveraging the geometric property of axis-aligned squares.
for y2 in y_points:Iterate over each candidate y-coordinate to explore potential squares.
This loop explores all vertical edges that could form squares with the query point, enabling systematic checking of all possible side lengths.
side = py - y2Calculate the side length of the potential square.
The side length is the vertical distance between the query point and the candidate point, which determines the horizontal offset for the other two vertices.
p3 = (px + side, py)Define the first candidate horizontal point on the right side.
This point, combined with the query point and vertical candidate, forms one corner of the square on the right side, essential for verifying square existence.
p4 = (px + side, y2)Define the second candidate horizontal point on the right side.
This point completes the square on the right side by connecting with the vertical candidate and the horizontal point.
p3 = (px - side, py)Define the first candidate horizontal point on the left side.
This point represents the potential square corner on the left side, mirroring the right side check to find all squares.
p4 = (px - side, y2)Define the second candidate horizontal point on the left side.
Completes the left-side square candidate, necessary for symmetric square detection.
res = 0Initialize the result accumulator for counting squares.
This variable accumulates the total number of squares found for the query point before adjusting for double counting.
Test Your Understanding
Why does the algorithm only iterate over points sharing the same x-coordinate as the query point when counting squares?
Because axis-aligned squares require vertical sides to share the same x-coordinate, iterating over points with the same x-coordinate identifies all possible vertical edges of squares with the query point, enabling efficient detection of complete squares.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Detect Squares from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Detect Squares drill