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.

#2013

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

检测正方形

给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：添加一个在数据流中的新点到某个数据结构中。可以添加重复的点，并会视作不同的点进行处理。给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个面积为正的轴对齐正方形，统计满足该要求的方…

数组哈希表设计计数

题目描述

给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：

添加一个在数据流中的新点到某个数据结构中。可以添加重复的点，并会视作不同的点进行处理。
给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ，统计满足该要求的方案数目。

轴对齐正方形 是一个正方形，除四条边长度相同外，还满足每条边都与 x-轴或 y-轴平行或垂直。

实现 DetectSquares 类：

DetectSquares() 使用空数据结构初始化对象
void add(int[] point) 向数据结构添加一个新的点 point = [x, y]
int count(int[] point) 统计按上述方式与点 point = [x, y] 共同构造 轴对齐正方形 的方案数。

示例：

输入：
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
输出：
[null, null, null, null, 1, 0, null, 2]

解释：
DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // 返回 1 。你可以选择：
// - 第一个，第二个，和第三个点
detectSquares.count([14, 8]); // 返回 0 。查询点无法与数据结构中的这些点构成正方形。
detectSquares.add([11, 2]); // 允许添加重复的点。
detectSquares.count([11, 10]); // 返回 2 。你可以选择：
// - 第一个，第二个，和第三个点
// - 第一个，第三个，和第四个点

提示：

point.length == 2
0 <= x, y <= 1000
调用 add 和 count 的 总次数 最多为 5000

lightbulb

解题思路

方法一：哈希表

我们可以用一个哈希表 $cnt$ 维护所有点的信息，其中 $cnt[x][y]$ 表示点 $(x, y)$ 的个数。

当调用 $add(x, y)$ 方法时，我们将 $cnt[x][y]$ 的值加 $1$ 。

当调用 $count(x_1, y_1)$ 方法时，我们需要获取另外的三个点，构成一个轴对齐正方形。我们可以枚举平行于 $x$ 轴且与 $(x_1, y_1)$ 的距离为 $d$ 的点 $(x_2, y_1)$ ，如果存在这样的点，根据这两个点，我们可以确定另外两个点为 $(x_1, y_1 + d)$ 和 $(x_2, y_1 + d)$ ，或者 $(x_1, y_1 - d)$ 和 $(x_2, y_1 - d)$ 。我们将这两种情况的方案数累加即可。

时间复杂度方面，调用 $add(x, y)$ 方法的时间复杂度为 $O(1)$ ，调用 $count(x_1, y_1)$ 方法的时间复杂度为 $O(n)$ ；空间复杂度为 $O(n)$ 。其中 $n$ 为数据流中的点的个数。

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

26

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2006 差的绝对值为 K 的数对数目 #2023 连接后等于目标字符串的字符串对 #2001 可互换矩形的组数