Find Nearest Point That Has the Same X or Y Coordinate

Easy
1109.

Find Nearest Point That Has the Same X or Y Coordinate

Find Nearest Point That Has the Same X or Y Coordinate is an easy coding problem on arrays and geometry, asked in Amazon and Google interviews.

You stand at (x, y) on a grid. points[i] = [a, b] is a point at (a, b). A point is valid when it shares your x-coordinate or your y-coordinate (a == x or b == y).

Return the index of the valid point with the smallest Manhattan distance |a - x| + |b - y| from you. If several valid points are equally close, return the smallest index among them. If no point is valid, return -1.

Example 1

Input
x = 5, y = 2, points = [[5,9],[1,2],[4,4],[5,3]]
Output
3
Explanation
Valid points are indices 0, 1 and 3 at distances 7, 4 and 1.

Example 2

Input
x = 2, y = 2, points = [[3,3]]
Output
-1

Example 3

Input
x = 1, y = 1, points = [[1,4],[4,1]]
Output
0
Explanation
Both are at distance 3; the smaller index wins.

Constraints

  • 1 <= points.length <= 10^4
  • points[i].length == 2
  • 1 <= x, y, a, b <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} x
 * @param {number} y
 * @param {number[][]} points
 * @return {number}
 */
var nearestValidPoint = function(x, y, points) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Nearest Point That Has the Same X or Y Coordinate Solution

Find Nearest Point That Has the Same X or Y Coordinate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find Nearest Point That Has the Same X or Y Coordinate is an easy coding problem on arrays and geometry, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Geometry
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You stand at (x, y) on a grid. points[i] = [a, b] is a point at (a, b). A point is valid when it shares your x-coordinate or your y-coordinate (a == x or b == y).

Return the index of the valid point with the smallest Manhattan distance |a - x| + |b - y| from you. If several valid points are equally close, return the smallest index among them. If no point is valid, return -1.

Example 1

Input: x = 5, y = 2, points = [[5,9],[1,2],[4,4],[5,3]]
Output: 3
Explanation: Valid points are indices 0, 1 and 3 at distances 7, 4 and 1.

Example 2

Input: x = 2, y = 2, points = [[3,3]]
Output: -1

Example 3

Input: x = 1, y = 1, points = [[1,4],[4,1]]
Output: 0
Explanation: Both are at distance 3; the smaller index wins.

Constraints

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

Hints for Find Nearest Point That Has the Same X or Y Coordinate

  1. Hint 1

    Skip every point that matches neither coordinate.

  2. Hint 2

    For the rest, compute the Manhattan distance and keep the best one seen so far.

  3. Hint 3

    Replace the best only on a strictly smaller distance, so ties keep the earlier index.

How to solve Find Nearest Point That Has the Same X or Y Coordinate

A single scan that filters out invalid points and keeps the closest valid one answers the question; the strict comparison handles the tie rule for free.

Approach

  1. Set best = -1 and bestDist to a value larger than any distance.
  2. For each index i: if a == x or b == y, compute d = |a - x| + |b - y|.
  3. If d < bestDist, record best = i and bestDist = d.
  4. Return best.

Why it works

Indices are visited in increasing order, and a later point replaces the current best only when it is strictly closer. So among the closest valid points, the first one found — the smallest index — is kept. If no point is valid, best is never set.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Use <, not <=, or ties return the largest index.
  • A point equal to (x, y) is valid with distance 0.
  • Return the index, not the distance or the point.

Reference solution

Python

from typing import List

def nearestValidPoint(x: int, y: int, points: List[List[int]]) -> int:
    best, best_dist = -1, None
    for i, (a, b) in enumerate(points):
        if a == x or b == y:
            d = abs(a - x) + abs(b - y)
            if best_dist is None or d < best_dist:
                best, best_dist = i, d
    return best

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays