What is the key pattern in solving Maximum Points Inside the Square?

The key pattern is array scanning combined with hash lookup. This helps efficiently compute the maximum number of points inside a valid square while ensuring no duplicate tags.

How does sorting improve the solution for this problem?

Sorting helps by reducing unnecessary comparisons during the scanning phase. It optimizes the search for potential square boundaries and tag uniqueness.

What is the time complexity of the brute force solution?

The brute force solution could have a time complexity of O(n^2), where n is the number of points, as it involves checking each point against every other point.

How do you ensure tag uniqueness within the square?

By using a hash table, you can efficiently track the tags within the current square and check for duplicates in constant time.

What happens if no valid square can be formed?

If no valid square can be formed, the result will be 0, as no points can be enclosed within a square that satisfies the tag uniqueness constraint.

#3143

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

正方形中的最多点数

给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标， s[i] 表示第 i 个点的标签。如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内不存在标签相同的两个点，那么我们称这个正方形是合法的。请你返回合法正方…

数组哈希表字符串二分查找排序

题目描述

给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的标签。

如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内不存在标签相同的两个点，那么我们称这个正方形是合法的。

请你返回合法正方形中可以包含的最多点数。

注意：

如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
正方形的边长可以为零。

示例 1：

输入：points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"

输出：2

解释：

边长为 4 的正方形包含两个点 points[0] 和 points[1] 。

示例 2：

输入：points = [[1,1],[-2,-2],[-2,2]], s = "abb"

输出：1

解释：

边长为 2 的正方形包含 1 个点 points[0] 。

示例 3：

输入：points = [[1,1],[-1,-1],[2,-2]], s = "ccd"

输出：0

解释：

任何正方形都无法只包含 points[0] 和 points[1] 中的一个点，所以合法正方形中都不包含任何点。

提示：

1 <= s.length, points.length <= 10⁵
points[i].length == 2
-10⁹ <= points[i][0], points[i][1] <= 10⁹
s.length == points.length
points 中的点坐标互不相同。
s 只包含小写英文字母。

lightbulb

解题思路

方法一：哈希表 + 排序

对于一个点 $(x, y)$ ，我们可以将其映射到以原点为中心的第一象限，即 $(\max(|x|, |y|), \max(|x|, |y|))$ 。这样，我们就可以将所有的点映射到第一象限，然后按照点到原点的距离进行排序。

我们可以使用哈希表 $g$ 来存储所有点到原点的距离，然后按照距离进行排序。对于每个距离 $d$ ，我们将所有距离为 $d$ 的点放在一起，然后遍历这些点，如果有两个点的标签相同，那么这个正方形是不合法的，直接返回答案。否则，我们将这些点加入到答案中。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        g = defaultdict(list)
        for i, (x, y) in enumerate(points):
            g[max(abs(x), abs(y))].append(i)
        vis = set()
        ans = 0
        for d in sorted(g):
            idx = g[d]
            for i in idx:
                if s[i] in vis:
                    return ans
                vis.add(s[i])
            ans += len(idx)
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for a clear understanding of how to calculate the minimal square edge length for each point.
question_mark
Evaluate the candidate's ability to optimize the brute force approach using sorting or hashing.
question_mark
Check for knowledge of how to efficiently track tag uniqueness within squares.

warning

常见陷阱

外企场景

error
Overlooking the tag uniqueness constraint, which can lead to invalid square selections.
error
Using inefficient algorithms that do not scale well with large inputs.
error
Failing to properly handle edge cases such as when points are too close to each other or when no valid squares can be formed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow squares to be rotated and test how that changes the computation.
arrow_right_alt
Use a different geometric shape for the boundary instead of a square.
arrow_right_alt
Extend the problem to higher dimensions or add more constraints on the square's location.

help

常见问题

外企场景

继续练习

#3186 施咒的最大总伤害 #3035 回文字符串的最大数量 #2933 高访问员工