How do you solve Detect Squares?

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.

What pattern does Detect Squares use?

The Pattern: Hash Maps (Frequency Counting with Coordinate Grouping) The Heuristic: 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.

Detect Squares — Hash Maps

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

Input: add([3, 10]), add([11, 2]), add([3, 2]), count([11, 10])

Output: 1

After 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1import collections
2
3class DetectSquares:
  def __init__(self):
      self.pts_count = collections.defaultdict(int)
      
  def add(self, point: list[int]) -> None:
      self.pts_count[tuple(point)] += 1
9
  def count(self, point: list[int]) -> int:
      res = 0
      px, py = point
      
      y_points = [y for x_val, y in self.pts_count if x_val == px and y != py]
15
      for y2 in y_points:
          side = py - y2
          
          p3 = (px + side, py)
          p4 = (px + side, y2)
          if p3 in self.pts_count and p4 in self.pts_count:
              res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]
          
          p3 = (px - side, py)
          p4 = (px - side, y2)
          if p3 in self.pts_count and p4 in self.pts_count:
              res += self.pts_count[(px, y2)] * self.pts_count[p3] * self.pts_count[p4]
      return res // 2 

Step-by-Step Solution

1

Store Points with Frequency Counts Using a Hash Map

5self.pts_count = collections.defaultdict(int)
8self.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.

2

Identify Candidate Vertical Points Sharing Query X-Coordinate

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.

3

Calculate Side Lengths and Check for Complementary Points to Complete Squares

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.

4

Return Half the Accumulated Count to Correct Double Counting

To adjust the final count by dividing by two, correcting for double counting of squares due to symmetric checks.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 28 Critical

return res // 2

Return 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.

Line 8 Critical

self.pts_count[tuple(point)] += 1

Increment 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.

Line 21 Critical

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.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does the algorithm only iterate over points sharing the same x-coordinate as the query point when counting squares?

See the answer with Pro.

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

or drill a free problem

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`