Find Nearest Point That Has The Same X Or Y Coordinate - Leetcode Solution

Problem Statement:

Given a list of points in a 2D plane, find the nearest point that has the same x or y coordinate as the given point.

Example:

Input: points = [[1,2],[3,1],[2,4],[2,3],[4,4]] Output: 2 Explanation: Point (2,3) is the nearest point that has the same x or y coordinate as (3,1).

Solution:

To solve this problem, we can iterate over the list of points. For each point, we can find the nearest point that has the same x or y coordinate using the following steps:

• Initialize minimum distance as infinity and nearest point as None.
• For each point, calculate the distance between the point and all other points.
• If the x coordinate of the point is the same as the current point or the y coordinate of the point is the same as the current point, and the distance between the two points is less than the minimum distance, update the minimum distance and nearest point.
• Return the nearest point.

Here's the Python code for this solution:

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        min_dist = float('inf')
        nearest_point = None
        
        for i, point in enumerate(points):
            if point[0] == x or point[1] == y:
                dist = abs(point[0] - x) + abs(point[1] - y)
                if dist < min_dist:
                    min_dist = dist
                    nearest_point = i
                    
        return nearest_point if nearest_point is not None else -1

In this solution, we have a class called Solution that contains a function called nearestValidPoint. The function takes three arguments - x, y, and points. x and y are the x and y coordinates of the given point, and points is a list of points in the 2D plane.

The function initializes min_dist as infinity and nearest_point as None. We then iterate over the list of points using enumerate to get the index of each point as well as the point itself.

For each point, we check if its x coordinate is the same as x or its y coordinate is the same as y. If it is, we calculate the distance between the two points using the Manhattan distance formula (abs(point[0] - x) + abs(point[1] - y)). If this distance is less than min_dist, we update min_dist and nearest_point.

Finally, we return nearest_point if it is not None, else we return -1 (which indicates that no valid point was found).

1