Find Nearest Point That Has the Same X or Y Coordinate

Here is a Python solution using list comprehension and the built-in min function with a custom key function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        # Initialize an empty list for valid points
        valid_points = []

        # Loop through the points with their indices
        for i, point in enumerate(points):
            # If the point is valid (shares x or y coordinate)
            if x == point[0] or y == point[1]:
                # Calculate Manhattan distance
                distance = abs(point[0] - x) + abs(point[1] - y)
                # Add the distance and index to valid_points
                valid_points.append((distance, i))

        # If there are no valid points, return -1
        if not valid_points:
            return -1

        # Find the valid point with the smallest distance and index
        min_point = min(valid_points)

        # Return the index of the point
        return min_point[1]

In this solution:

1. We first filter for the valid points, which are the ones that share the same x or y coordinate as the current location. For each valid point, we calculate its Manhattan distance to the current location and store it along with its index in the array valid_points. This step is done using a list comprehension.

2. If valid_points is empty after the filtering, it means there are no valid points and we return -1.

3. Otherwise, we use the min function to find the valid point with the smallest Manhattan distance. Since valid_points is an array of tuples where the first element is the distance and the second element is the index, min will first compare the distances and then the indices. Therefore, if there are multiple points with the same smallest distance, the one with the smallest index will be returned.

The time complexity of this solution is O(n), where n is the number of points. This is because we need to iterate through the points once to filter the valid ones and calculate their distances. The space complexity is O(k), where k is the number of valid points, as we store these points in the valid_points array.

Q&A

HI, this is my solution that failed at testcase 101: Index 53 and 73 have the same value of [24,27], giving the smallest manhatten distance of 3 when x,y=27,27 However, my code kept giving the output of index 73 instead of 53. Is anyone able to spot what is wrong with my code?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
def nearestValidPoint(self, x, y, points):

    dict1={}
    for i in range(len(points)):
        if points[i][0]==x or points[i][1]==y:
            manhat=int(abs(points[i][0]-x)+abs(points[i][1]-y))
            dict1[i]=manhat

    if dict1:
        minmanhat=min(dict1.values())
        for k,v in dict1.items():
            if v==minmanhat:
                return(k)    
    else:
        return(-1)

Your approach to finding the valid point with the minimum Manhattan distance is correct. However, your approach to finding the smallest index isn’t quite right. When you find a minimum Manhattan distance, you’re not guaranteed to get the smallest index for it, because dictionaries in Python do not preserve any particular order of keys.

To ensure you get the smallest index, you should iterate over your dict1 in ascending order of the keys (which represent indices). Here’s how you could modify your code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution(object):
    def nearestValidPoint(self, x, y, points):
        dict1 = {}
        for i in range(len(points)):
            if points[i][0] == x or points[i][1] == y:
                manhat = abs(points[i][0] - x) + abs(points[i][1] - y)
                dict1[i] = manhat

        if dict1:
            minmanhat = min(dict1.values())
            # Sort the keys in ascending order before iterating over them
            for k in sorted(dict1.keys()):
                if dict1[k] == minmanhat:
                    return k
        else:
            return -1

This version of the code will return the smallest index among those that have the minimum Manhattan distance.