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^4points[i].length == 21 <= x, y, a, b <= 10^4
Hints for Find Nearest Point That Has the Same X or Y Coordinate
Hint 1
Skip every point that matches neither coordinate.
Hint 2
For the rest, compute the Manhattan distance and keep the best one seen so far.
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
- Set
best = -1andbestDistto a value larger than any distance. - For each index
i: ifa == xorb == y, computed = |a - x| + |b - y|. - If
d < bestDist, recordbest = iandbestDist = d. - 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 bestJava
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