Find Nearest Point That Has the Same X or Y Coordinate solution and explanation
Google
6 more videos on this problem
1779. Find Nearest Point That Has the Same X or Y Coordinate (Leetcode Easy)Programming Live with Larry · 2:56 · 2K views
1779 Find Nearest Point That Has the Same X or Y CoordinateMath Geeks · 3:55 · 1K views
LeetCode 1779. [easy] Find Nearest Point That Has the Same X or Y CoordinateFrancesco Manicardi · 1:56 · 1K views
Leetcode Biweekly Contest 47 | Problem 1779 , 1780 , 1781 | LEETCODE BIWEEKLYcode Explainer · 13:31 · 1K views
LeetCode | 1779. Find Nearest Point That Has the Same X or Y Coordinate | C++ SolutionRakib Ahasan · 2:36 · 560 views
LeetCode Programming Skills I - Day 03. 1779. Find Nearest Point That Has the Same X or Y CoordinateLeetCode The Hard Way · 3:50 · 295 views
1779. Find Nearest Point That Has the Same X or Y Coordinate - Javascript - Time: O(n) Space: O(1)Aaron Sadino Coding · 15:16 · 217 views
The problem
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 each 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).
Example 1:
Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]] Output: 2 Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.
Example 2:
Input: x = 3, y = 4, points = [[3,4]] Output: 0 Explanation: The answer is allowed to be on the same location as your current location.
Example 3:
Input: x = 3, y = 4, points = [[2,3]] Output: -1 Explanation: There are no valid points.
Constraints:
1 <= points.length <= 104points[i].length == 21 <= x, y, ai, bi <= 104
Approach overview
Problem Overview: You are given your current location (x, y) and a list of points. A point is considered valid if it shares the same x coordinate or the same y coordinate. Among all valid points, return the index of the point with the smallest Manhattan distance from your location. If multiple points have the same distance, return the smallest index.
Approach 1: Iterative Approach Using Manhattan Distance (O(n) time, O(1) space)
Scan the array once and evaluate each point. A point is valid if px == x or py == y. For valid points, compute the Manhattan distance using |px - x| + |py - y|. Track the smallest distance seen so far along with its index. Because the scan proceeds from left to right, the first occurrence naturally preserves the smallest index when distances tie. This approach uses a simple loop and constant extra memory, making it optimal for problems involving array traversal.
Approach 2: Filter Valid Points and Find Minimum (O(n) time, O(n) space)
First filter the list to keep only points that share the same x or y coordinate. For each valid point, compute the Manhattan distance and store a tuple of (distance, index). After filtering, select the tuple with the smallest distance (and smallest index in case of ties). Many languages allow concise implementations using functional utilities such as filter, list comprehensions, or streams. This version separates validation from distance computation, which can improve readability when working with coordinate-based array problems or simple geometry logic.
Recommended for interviews: The single-pass iterative solution is what interviewers expect. It demonstrates you understand Manhattan distance and can solve the problem in one linear scan with constant space. The filtering approach is also linear but introduces extra memory and abstraction layers. Showing the direct scan first proves you can reason about constraints and implement an optimal O(n) solution quickly.
Approach 1: Iterative Approach Using Manhattan Distance
This approach involves iterating through each point in the array to check if it is valid, i.e., it shares either the x or y coordinate with the given point (x, y). If it is valid, we calculate the Manhattan distance from (x, y) to that point and update the minimum distance and corresponding index. Finally, we return the index of the point with the smallest distance.
def nearestValidPoint(x, y, points):
min_distance = float('inf')
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
index = i
return indexclass Solution {
public int nearestValidPoint(int x, int y, int[][] points) {
int minDistance = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < points.length; i++) {
if (points[i][0] == x || points[i][1] == y) {
int dist = Math.abs(x - points[i][0]) + Math.abs(y - points[i][1]);
if (dist < minDistance) {
minDistance = dist;
index = i;
}
}
}
return index;
}
}#include <vector>
#include <climits>
int nearestValidPoint(int x, int y, std::vector<std::vector<int>>& points) {
int minDistance = INT_MAX;
int index = -1;
for (int i = 0; i < points.size(); ++i) {
if (points[i][0] == x || points[i][1] == y) {
int dist = abs(x - points[i][0]) + abs(y - points[i][1]);
if (dist < minDistance) {
minDistance = dist;
index = i;
}
}
}
return index;
}var nearestValidPoint = function(x, y, points) {
let minDistance = Infinity;
let index = -1;
for (let i = 0; i < points.length; i++) {
let [a, b] = points[i];
if (a === x || b === y) {
let distance = Math.abs(x - a) + Math.abs(y - b);
if (distance < minDistance) {
minDistance = distance;
index = i;
}
}
}
return index;
};#include <stdio.h>
#include <stdlib.h>
int nearestValidPoint(int x, int y, int** points, int pointsSize, int* pointsColSize) {
int minDistance = __INT_MAX__;
int index = -1;
for (int i = 0; i < pointsSize; i++) {
int a = points[i][0];
int b = points[i][1];
if (a == x || b == y) {
int distance = abs(x - a) + abs(y - b);
if (distance < minDistance) {
minDistance = distance;
index = i;
}
}
}
return index;
}public class Solution {
public int NearestValidPoint(int x, int y, int[][] points) {
int minDistance = int.MaxValue;
int index = -1;
for (int i = 0; i < points.Length; i++) {
if (points[i][0] == x || points[i][1] == y) {
int distance = Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]);
if (distance < minDistance) {
minDistance = distance;
index = i;
}
}
}
return index;
}
}The Python solution iterates over the points array, identifying valid points, calculating their Manhattan distance, and keeping the index of the point with the minimum distance.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Use of Filter for Valid Points and Finding Minimum
This approach first filters out all invalid points, leaving only those that share the x or y coordinate with your position. After filtering, it computes the Manhattan distances for these valid points, finds the smallest distance, and returns the corresponding index.
def nearestValidPoint(x, y, points):
min_distance = float('inf')
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
index = i
return indexclass Solution {
public int nearestValidPoint(int x, int y, int[][] points) {
int minDistance = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < points.length; i++) {
if (points[i][0] == x || points[i][1] == y) {
int dist = Math.abs(x - points[i][0]) + Math.abs(y - points[i][1]);
if (dist < minDistance) {
minDistance = dist;
index = i;
}
}
}
return index;
}
}#include <vector>
#include <climits>
int nearestValidPoint(int x, int y, std::vector<std::vector<int>>& points) {
int minDist = INT_MAX, ans = -1;
for (int i = 0; i < points.size(); ++i) {
if (points[i][0] == x || points[i][1] == y) {
int dist = abs(x - points[i][0]) + abs(y - points[i][1]);
if (dist < minDist) {
minDist = dist;
ans = i;
}
}
}
return ans;
}var nearestValidPoint = function(x, y, points) {
let minDistance = Infinity;
let index = -1;
for (let i = 0; i < points.length; i++) {
let [a, b] = points[i];
if (a === x || b === y) {
let distance = Math.abs(x - a) + Math.abs(y - b);
if (distance < minDistance) {
minDistance = distance;
index = i;
}
}
}
return index;
};#include <stdio.h>
#include <stdlib.h>
int nearestValidPoint(int x, int y, int** points, int pointsSize, int* pointsColSize) {
int index = -1, minDistance = __INT_MAX__;
for (int i = 0; i < pointsSize; i++) {
int a = points[i][0], int b = points[i][1];
if (a == x || b == y) {
int distance = abs(x - a) + abs(y - b);
if (distance < minDistance) {
minDistance = distance;
index = i;
}
}
}
return index;
}public class Solution {
public int NearestValidPoint(int x, int y, int[][] points) {
int minDistance = int.MaxValue;
int index = -1;
for (int i = 0; i < points.Length; i++) {
if (points[i][0] == x || points[i][1] == y) {
int distance = Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]);
if (distance < minDistance) {
minDistance = distance;
index = i;
}
}
}
return index;
}
}In this Python solution, a filtered iteration finds valid points first, computes the manhattan distance, and records the index with minimal value similar to previous solutions.
Time Complexity: O(n), n is the number of points.
Space Complexity: O(1).
Approach 3: Default Approach
function nearestValidPoint(x: number, y: number, points: number[][]): number {
let res = -1;
let midDif = Infinity;
points.forEach(([px, py], i) => {
if (px != x && py != y) {
return;
}
const dif = Math.abs(px - x) + Math.abs(py - y);
if (dif < midDif) {
midDif = dif;
res = i;
}
});
return res;
}func nearestValidPoint(x int, y int, points [][]int) int {
ans, mi := -1, 1000000
for i, p := range points {
a, b := p[0], p[1]
if a == x || b == y {
d := abs(a-x) + abs(b-y)
if d < mi {
ans, mi = i, d
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn nearest_valid_point(x: i32, y: i32, points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
let mut min_dif = i32::MAX;
let mut res = -1;
for i in 0..n {
let (p_x, p_y) = (points[i][0], points[i][1]);
if p_x != x && p_y != y {
continue;
}
let dif = (p_x - x).abs() + (p_y - y).abs();
if dif < min_dif {
min_dif = dif;
res = i as i32;
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach Using Manhattan Distance | Time Complexity: O(n). |
| Use of Filter for Valid Points and Finding Minimum | Time Complexity: O(n), n is the number of points. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Manhattan Distance Scan | O(n) | O(1) | Best general solution. Single pass through the array with minimal memory. |
| Filter Valid Points Then Compute Minimum | O(n) | O(n) | Useful for cleaner functional-style code or when separating validation and computation logic. |
Frequently asked questions
Is Find Nearest Point That Has the Same X or Y Coordinate easy or hard?
Find Nearest Point That Has the Same X or Y Coordinate is classified as an Easy problem on LeetCode. The task mainly tests understanding of Manhattan distance and basic array traversal. The optimal solution requires a straightforward O(n) scan with constant extra space.
Find Nearest Point That Has the Same X or Y Coordinate Python/Java solution
In Python or Java, iterate through the list of points and check if px == x or py == y. For valid points compute |px - x| + |py - y| and update the minimum distance if the value is smaller. Maintain the index of the best candidate during traversal to return the correct result.
How to solve Find Nearest Point That Has the Same X or Y Coordinate in O(n)?
Iterate through the array of points and check if the point shares the same x or y coordinate. If it does, compute the Manhattan distance using |px - x| + |py - y|. Keep track of the smallest distance and update the answer when a smaller distance is found. This single linear scan ensures O(n) time complexity.
What is the best approach for Find Nearest Point That Has the Same X or Y Coordinate?
The best approach is a single-pass iteration through the points while computing Manhattan distance for valid points. A point is valid if it shares the same x or y coordinate with the target location. Track the minimum distance and index during the scan. This runs in O(n) time and O(1) space.
Is Find Nearest Point That Has the Same X or Y Coordinate asked at Google/Amazon/Meta?
This problem represents a common array scanning and coordinate filtering pattern frequently used in coding interviews. Variants of Manhattan distance and coordinate matching appear in interviews at large tech companies such as Google, Amazon, and Meta as part of easy or warm‑up questions.
What data structure is used in Find Nearest Point That Has the Same X or Y Coordinate?
The primary data structure is an array of coordinate pairs. The algorithm performs a simple linear traversal of the array while computing Manhattan distance and tracking the minimum value. No additional data structures such as hash maps or heaps are required for the optimal solution.
What is the time complexity of Find Nearest Point That Has the Same X or Y Coordinate?
The optimal solution runs in O(n) time because each point is checked exactly once. The algorithm simply validates coordinates and calculates Manhattan distance. Space complexity is O(1) since only a few variables are used to track the best distance and index.