Find Nearest Point That Has the Same X or Y Coordinate
Here is a Python solution using list comprehension and the builtin min
function with a custom key function.


In this solution:
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.If
valid_points
is empty after the filtering, it means there are no valid points and we return 1.Otherwise, we use the
min
function to find the valid point with the smallest Manhattan distance. Sincevalid_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?


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:


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