Problem Description

You are given the coordinates of a point (x, y) and an array points where each element is also a pair of coordinates [a, b]. Your task is to find the index of the nearest point in points that has either the same x-coordinate or the same y-coordinate as (x, y). The distance is measured using the Manhattan distance, defined as |x - a| + |y - b|.

• If there are multiple valid points with the same minimum distance, return the one with the smallest index.
• If no such point exists, return -1.
• You must not reuse the target point itself if it appears in points (unless allowed by the problem statement).

Constraints:
1 <= points.length <= 10^4
points[i].length == 2
-10^4 <= x, y, a, b <= 10^4

Thought Process

The main challenge is to efficiently find the point that shares either the x or y coordinate with the target and is closest in Manhattan distance. A brute-force approach would be to check every point in the list, but we should also consider if there's a way to optimize by pre-filtering or using data structures.

• Start by iterating through each point and checking if it shares the x or y coordinate.
• If it does, compute the Manhattan distance and keep track of the minimum found so far.
• If multiple points have the same minimum distance, choose the one that appears first (smallest index).
• Since the constraints are moderate, a linear scan is acceptable, but always consider if a map or grouping could help for larger constraints.

For this problem, the brute-force method is simple and effective, but it's important to reason about why it's sufficient and when optimizations might be necessary.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize tracking variables:
   • Set min_distance to a very large value (like infinity).
   • Set result_index to -1 to indicate "not found" by default.
2. Iterate through the points array:
   • For each points[i] = [a, b], check if a == x or b == y.
   • If neither matches, skip to the next point.
3. Compute Manhattan Distance:
   • If the point is valid, calculate distance = |x - a| + |y - b|.
4. Update the closest point:
   • If distance < min_distance, update min_distance and result_index to the current index.
   • If distance == min_distance but current index is smaller, update result_index.
5. Return the result:
   • After the loop, return result_index.

This approach is efficient because it only requires a single pass through the points array and uses constant extra space.

Example Walkthrough

Given:
x = 3, y = 4
points = [[1,2],[3,1],[2,4],[2,3],[4,4]]

1. [1,2]: x ≠ 3, y ≠ 4 → skip
2. [3,1]: x = 3 → valid. Distance = |3-3| + |4-1| = 3. min_distance = 3, result_index = 1
3. [2,4]: y = 4 → valid. Distance = |3-2| + |4-4| = 1. min_distance = 1, result_index = 2
4. [2,3]: x ≠ 3, y ≠ 4 → skip
5. [4,4]: y = 4 → valid. Distance = |3-4| + |4-4| = 1. min_distance = 1, but result_index stays 2 since 2 < 4.

Final output: 2 (the index of [2,4]).

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N) where N is the number of points, since we check each point once.
  • Space Complexity: O(1) extra space, as we only track a few variables.
• Optimized approaches:
  • For this problem, brute-force is already optimal given the constraints. Using hash maps or grouping would not improve the asymptotic complexity, but could help if we had to answer multiple queries efficiently.

Summary

This problem demonstrates how a direct, linear scan can be both simple and optimal when constraints are reasonable. The key insights are:

• Filter points by coordinate match before considering distance.
• Update the result based on minimum distance and smallest index.
• Manhattan distance is efficient to compute and suits grid-based problems.

Code Implementation

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

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int min_distance = INT_MAX;
        int result_index = -1;
        for (int i = 0; i < points.size(); ++i) {
            int a = points[i][0], b = points[i][1];
            if (a == x || b == y) {
                int distance = abs(x - a) + abs(y - b);
                if (distance < min_distance) {
                    min_distance = distance;
                    result_index = i;
                }
            }
        }
        return result_index;
    }
};
      

class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        int minDistance = Integer.MAX_VALUE;
        int resultIndex = -1;
        for (int i = 0; i < points.length; i++) {
            int a = points[i][0], b = points[i][1];
            if (a == x || b == y) {
                int distance = Math.abs(x - a) + Math.abs(y - b);
                if (distance < minDistance) {
                    minDistance = distance;
                    resultIndex = i;
                }
            }
        }
        return resultIndex;
    }
}
      

var nearestValidPoint = function(x, y, points) {
    let minDistance = Infinity;
    let resultIndex = -1;
    for (let i = 0; i < points.length; i++) {
        const [a, b] = points[i];
        if (a === x || b === y) {
            const distance = Math.abs(x - a) + Math.abs(y - b);
            if (distance < minDistance) {
                minDistance = distance;
                resultIndex = i;
            }
        }
    }
    return resultIndex;
};