What is the Manhattan distance in this problem?

The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as abs(x1 - x2) + abs(y1 - y2).

How do I handle the case where no valid points exist?

If no valid points are found, return -1 to indicate that no point shares the same x or y coordinate as your current position.

What is the correct approach to handle ties in the Manhattan distance?

If multiple points have the same smallest Manhattan distance, return the point that appears first in the array (i.e., with the smallest index).

How does the 'Find Nearest Point That Has the Same X or Y Coordinate' problem relate to the Array-driven solution strategy?

This problem is solved using an Array-driven strategy by iterating through the array of points and checking each point’s validity based on its coordinates.

What is the time complexity of the solution?

The time complexity of the solution is O(n), where n is the number of points in the array, as we check each point once.

#1779

Easy

auto_awesome数组·driven

LeetCode 题解工作台

找到最近的有相同 X 或 Y 坐标的点

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [a i , b i ] 表示在 (a i , b i ) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称…

数组

题目描述

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [a_i, b_i] 表示在 (a_i, b_i) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。

请返回距离你当前位置 曼哈顿距离 最近的有效点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标最小的一个。如果没有有效点，请返回 -1 。

两个点 (x₁, y₁) 和 (x₂, y₂) 之间的 曼哈顿距离 为 abs(x₁ - x₂) + abs(y₁ - y₂) 。

示例 1：

输入：x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
输出：2
解释：所有点中，[3,1]，[2,4] 和 [4,4] 是有效点。有效点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1 。[2,4] 的下标最小，所以返回 2 。

示例 2：

输入：x = 3, y = 4, points = [[3,4]]
输出：0
提示：答案可以与你当前所在位置坐标相同。

示例 3：

输入：x = 3, y = 4, points = [[2,3]]
输出：-1
解释：没有 有效点。

提示：

1 <= points.length <= 10⁴
points[i].length == 2
1 <= x, y, a_i, b_i <= 10⁴

lightbulb

解题思路

方法一：直接遍历

直接遍历 points 数组，对于 $points[i]$ ，如果 $points[i][0] = x$ 或者 $points[i][1] = y$ ，则说明 $points[i]$ 是有效点，计算曼哈顿距离，更新最小距离和最小距离的下标。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为 points 数组的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        ans, mi = -1, inf
        for i, (a, b) in enumerate(points):
            if a == x or b == y:
                d = abs(a - x) + abs(b - y)
                if mi > d:
                    ans, mi = i, d
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient iteration through the array with minimal space usage.
question_mark
Ensure the candidate handles edge cases like no valid points correctly.
question_mark
Pay attention to how the candidate manages ties in Manhattan distance when multiple points are valid.

warning

常见陷阱

外企场景

error
Not checking both x and y coordinates to determine if a point is valid.
error
Failing to account for cases where no valid points exist, which should return -1.
error
Incorrectly handling ties in Manhattan distance and not returning the point with the smallest index.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the grid is large, and the points array contains a high number of elements?
arrow_right_alt
How would the solution change if the grid was multidimensional or 3D?
arrow_right_alt
How can this problem be adapted to find the furthest point instead of the nearest?

help

常见问题

外企场景

继续练习

#1776 车队 II #1782 统计点对的数目 #1775 通过最少操作次数使数组的和相等