Find Nearest Point That Has the Same X or Y Coordinate

easy array scan

Problem

Given a point (x, y) and a list of points, return the index of the closest valid point — same x or same y — by Manhattan distance, smallest index on tie. Return −1 if none.

Inputx = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]

Output2

Points 1 (same x=3), 2 (same y=4), and 4 (same y=4) are valid; distances 3, 1, 1; idx 2 wins (lower).

points (x,y;...)

def nearest_valid_point(x, y, points):
    best = -1
    best_d = float('inf')
    for i, (px, py) in enumerate(points):
        if px == x or py == y:
            d = abs(px - x) + abs(py - y)
            if d < best_d:
                best_d = d
                best = i
    return best

function nearestValidPoint(x, y, points) {
  let best = -1, bestD = Infinity;
  for (let i = 0; i < points.length; i++) {
    const [px, py] = points[i];
    if (px === x || py === y) {
      const d = Math.abs(px - x) + Math.abs(py - y);
      if (d < bestD) { bestD = d; best = i; }
    }
  }
  return best;
}

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

int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
    int best = -1, bestD = INT_MAX;
    for (int i = 0; i < (int)points.size(); i++) {
        if (points[i][0] == x || points[i][1] == y) {
            int d = abs(points[i][0] - x) + abs(points[i][1] - y);
            if (d < bestD) { bestD = d; best = i; }
        }
    }
    return best;
}

Explanation

We only care about points that share a row or a column with our location (x, y) — that is, the same x or the same y. Among those valid points, we want the one closest by Manhattan distance, and on a tie we keep the smallest index.

The solution is a straightforward single scan. We keep two trackers: best (the index of the closest valid point so far, starting at -1) and best_d (its distance, starting at infinity).

For each point (px, py) we first check validity with px == x or py == y. If valid, its distance is abs(px - x) + abs(py - y). We update best only when this distance is strictly smaller than best_d — using strictly-less keeps the earliest index on a tie automatically.

Example: x = 3, y = 4, points [[1,2],[3,1],[2,4],[2,3],[4,4]]. Point 1 shares x=3 (distance 3), point 2 shares y=4 (distance 1), point 4 shares y=4 (distance 1). Point 2 reaches distance 1 first, so it wins and the answer is 2.

If no point qualifies, best never changes and we correctly return -1.

Time: O(n) Space: O(1)