Find Nearest Point That Has the Same X or Y Coordinate

Difficulty: Easy | Acceptance: 70.00% | Paid: No Topics: Array

You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where points[i] = [ai, bi] represents that a point exists at (ai, bi). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.

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

• Examples
• Constraints
• Linear Scan
• Functional Approach

Examples

Example 1:

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: The valid points are [3,1], [2,4], and [4,4].
The point with the smallest Manhattan distance is [2,4] with a distance of 1.

Example 2:

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The point [3,4] is valid and has the smallest distance of 0.

Example 3:

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.

Constraints

1 <= points.length <= 10⁴
points[i].length == 2
1 <= x, y, ai, bi <= 10⁴

Linear Scan

Intuition We iterate through the list of points once. For each point, we check if it is valid (shares x or y). If it is, we calculate its Manhattan distance to the target. We keep track of the smallest distance found so far and the corresponding index.

Steps

• Initialize min_dist to infinity and ans to -1.
• Iterate through the points array using the index i.
• For each point (a, b), check if a == x or b == y.
• If valid, calculate dist = abs(a - x) + abs(b - y).
• If dist < min_dist, update min_dist to dist and ans to i.
• Return ans after the loop finishes.

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: list[list[int]]) -> int:
        min_dist = float('inf')
        ans = -1
        for i, (a, b) in enumerate(points):
            if a == x or b == y:
                dist = abs(a - x) + abs(b - y)
                if dist < min_dist:
                    min_dist = dist
                    ans = i
        return ans

Complexity

• Time: O(n), where n is the number of points. We visit each point exactly once.
• Space: O(1). We only use a few variables for storage.
• Notes: This is the most optimal approach for this problem.

Functional Approach

Intuition We utilize functional programming constructs like filter, map, and reduce (or their language-specific equivalents) to process the array. This approach filters for valid points first, then finds the one with the minimum distance.

Steps

• Filter the array to keep only points where x or y matches.
• Transform the remaining points to include their original index and calculated distance.
• Reduce the collection to find the entry with the smallest distance (and smallest index in case of ties).
• Return the index or -1 if the filtered list is empty.

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: list[list[int]]) -> int:
        def get_dist(i):
            a, b = points[i]
            return abs(a - x) + abs(b - y)
        
        valid_indices = [i for i, (a, b) in enumerate(points) if a == x or b == y]
        if not valid_indices:
            return -1
        return min(valid_indices, key=get_dist)

Complexity

• Time: O(n). We still need to examine every element to filter or find the minimum.
• Space: O(n) in the worst case for languages that create intermediate arrays (like Python list comprehensions or Java Streams), though O(1) is possible with specific reductions.
• Notes: While often more concise, functional approaches can sometimes have higher constant factors or memory overhead compared to a simple loop.