Problem Description

You are provided with your current coordinates (x, y) on a Cartesian grid. Additionally, you are given a list of points, each represented by a pair of coordinates [a_i, b_i]. A point is considered valid if it has either the same x-coordinate as yours (shares the same vertical line) or the same y-coordinate (shares the same horizontal line). The goal is to find the closest valid point to you based on the Manhattan distance. The Manhattan distance between two points (x_1, y_1) and (x_2, y_2) is given by abs(x_1 - x_2) + abs(y_1 - y_2), where abs stands for the absolute value function.

You need to return the smallest 0-indexed position of a point from the list that is valid and has the smallest Manhattan distance from your current location. If there is more than one valid point at the same minimum distance, return the one with the smallest index. If no valid points exist, return -1.

Intuition

To solve this problem, the straightforward approach is to iterate through the list of points, check for the conditions of validity (same x-coordinate or y-coordinate), and calculate the Manhattan distance between each valid point and your current coordinates.

While iterating, two things must be done:

1. Check if the current point is valid by comparing its coordinates with your coordinates (x, y).
2. If valid, compute the Manhattan distance to the current point.

We maintain two variables, mi to track the minimum distance found so far, and ans to store the index of the point with that minimum distance. By default, mi is set to infinity (inf) as we are looking for the minimum distance, and ans is set to -1 in case there are no valid points.

Each time we find a valid point with a Manhattan distance less than mi, we update mi with that distance and ans with the current index.

After iterating through all points, we simply return ans, which holds the index of the nearest valid point, or -1 if no valid point was found.

Solution Approach

The implementation of the solution uses a simple iterative approach with none of the more advanced algorithms or patterns. The main data structures used are the Python list to hold the points and a tuple to work with individual point coordinates.

Here's the breakdown of the implementation:

1. Initialize ans variable to -1. This will hold the index of the closest valid point, and if it stays -1, it means no valid point was found.

2. Initialize mi variable to inf (stands for infinity in Python), which will keep track of the smallest Manhattan distance found during iteration.

3. Iterate over each point using enumerate to get both the index i and the coordinates (a, b).

4. Check if the current point is valid by comparing either the x-coordinate or the y-coordinate with the current location. This is done with the condition if a == x or b == y:.

5. If the point is valid, compute its Manhattan distance from the current location with d = abs(a - x) + abs(b - y).

6. Compare the calculated distance d with the current minimum distance mi. If d is smaller, update mi to the new minimum distance and ans to the current index.

7. After exiting the loop, return ans, which represents the index of the point with the smallest Manhattan distance, or -1 if no valid point was found.

This approach ensures that we are only considering valid points and always choose the valid point that is closest to the current location. Furthermore, since we update ans only when we find a closer valid point, if there are multiple points with the same distance, the first one found (and thus with the smallest index) will be chosen, consistent with the problem's requirement.

Example Walkthrough

Let's consider an example to illustrate the solution approach:

• Your current coordinates: (1, 2)
• List of points: [[0, 3], [1, 9], [2, 3], [1, 4], [0, 2]]

Following the steps outlined in the solution approach:

1. Initialize ans to -1.

2. Initialize mi to inf.

3. Start iterating over the list of points:

   • Index 0, Point [0, 3]: It's not valid since neither 0 == 1 nor 3 == 2. Move to the next point.
   • Index 1, Point [1, 9]: This point is valid because it shares the same x-coordinate as yours (1 == 1). Calculate the Manhattan distance: d = abs(1 - 1) + abs(9 - 2) = 7. As d is smaller than mi, update mi to 7 and ans to 1.
   • Index 2, Point [2, 3]: It's not valid since neither 2 == 1 nor 3 == 2. Move to the next point.
   • Index 3, Point [1, 4]: This point is valid (1 == 1). Calculate the Manhattan distance: d = abs(1 - 1) + abs(4 - 2) = 2. Update mi to 2 and ans to 3 since 2 is smaller than the current mi of 7.
   • Index 4, Point [0, 2]: This point is valid (2 == 2). Calculate the Manhattan distance: d = abs(0 - 1) + abs(2 - 2) = 1. Update mi to 1 and ans to 4 since 1 is smaller than the current mi of 2.

4. Finish the iteration.

5. Return ans which is 4 as this is the point [0, 2] with the smallest Manhattan distance from your current location (1, 2).

Using this example, we can see that the solution methodology effectively finds the closest valid point from the given list. It also displays that if multiple valid points have the same minimum distance, it shall return the point with the smallest index.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the number of points in the input list points. This is because the function iterates through the list of points exactly once, performing a constant amount of work for each point by checking whether the point is valid and calculating the Manhattan distance if necessary.

Space Complexity

The space complexity of the code is O(1). The extra space used by the algorithm includes a fixed number of integer variables (ans, mi, a, b, d), which do not depend on the size of the input. Since the amount of extra space required does not scale with the input size, the space complexity is constant.

Learn more about how to find time and space complexity quickly using problem constraints.