#2013

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Detect Squares

Detect Squares requires tracking points on a 2D plane to quickly count all possible axis-aligned squares using efficient hash-based lookup.

array hash table design counting

Problem Statement

You are given a stream of points on the X-Y plane. Implement a data structure that supports adding points and counting how many axis-aligned squares can be formed with a given query point. An axis-aligned square has edges parallel or perpendicular to the x-axis and y-axis, and all edges must have equal length.

Design a DetectSquares class with two methods: add(point) to store a new point, allowing duplicates, and count(point) to return the number of squares that can be formed using the given point as one vertex. Points coordinates range from 0 to 1000, and the total number of add and count calls does not exceed 3000.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 Approach

Use a Hash Map to Track Point Frequencies

Maintain a nested hash map where the first key is the x-coordinate and the second key is the y-coordinate. Store the frequency of each point to quickly handle duplicate points and enable constant-time checks during counting.

Scan Along Shared Coordinates

For a count query, iterate over all points that share the same x or y coordinate with the query point. For each candidate, compute the side length and determine the positions of the other two vertices, then use the hash map to verify if they exist.

Sum Square Counts Efficiently

Multiply the frequencies of the points at the other two vertices when valid. Accumulate these products to get the total number of squares. This approach ensures duplicate points contribute correctly without redundant recalculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Adding a point is O(1) because it updates the hash map. Counting squares requires scanning points along the same x or y coordinate and performing O(1) hash lookups for potential vertices, so worst-case time is O(n) where n is the number of points sharing coordinates. Space is O(p) where p is the number of distinct points stored.

What Interviewers Usually Probe

Asks about handling duplicate points and counting their contribution to squares.
Probes understanding of hash map use for constant-time lookup in geometric problems.
Checks if candidate points are scanned efficiently along shared coordinates rather than all points.

Common Pitfalls or Variants

Common pitfalls

Failing to account for duplicate points when counting squares, leading to undercounting.
Iterating over all stored points instead of only those sharing x or y coordinates, causing slow queries.
Incorrectly calculating positions of the other two square vertices, missing valid squares.

Follow-up variants

Count rectangles instead of squares using similar hash map frequency logic.
Handle dynamic deletion of points while still efficiently counting squares.
Extend to 3D to count axis-aligned cubes using a three-level nested hash map.

FAQ

What is the key pattern used in Detect Squares?

The problem relies on array scanning along shared coordinates combined with hash lookups to verify the existence of potential square vertices.

Can duplicate points affect the square count?

Yes, duplicates increase the number of valid squares. Each duplicate point is counted according to its frequency in the hash map.

What are the time complexity trade-offs?

Adding a point is O(1), but counting squares depends on the number of points sharing coordinates with the query point, potentially O(n) in worst cases.

Why use a hash map instead of an array for counts?

A hash map enables constant-time lookup for any point and handles duplicates efficiently without scanning all points.

How does GhostInterview improve solving Detect Squares?

It guides tracking point frequencies, optimizes candidate scanning, and correctly handles duplicates, ensuring accurate and fast square counts.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $cnt$ to maintain all the information of the points, where $cnt[x][y]$ represents the count of point $(x, y)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class DetectSquares:
    def __init__(self):
        self.cnt = defaultdict(Counter)

    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
        ans = 0
        for x2 in self.cnt.keys():
            if x2 != x1:
                d = x2 - x1
                ans += self.cnt[x2][y1] * self.cnt[x1][y1 + d] * self.cnt[x2][y1 + d]
                ans += self.cnt[x2][y1] * self.cnt[x1][y1 - d] * self.cnt[x2][y1 - d]
        return ans


# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)

Continue Practicing

#2006 count number of pairs with absolute difference k #2023 number of pairs of strings with concatenation equal to target #2001 number of pairs of interchangeable rectangles