algoadvance

Given your location on a 2D grid (x, y), determine the Manhattan distance from your location to the closest point that has either the same x-coordinate or the same y-coordinate as your location. If there are multiple such points, return the smallest index (0-based) of these points. If no such point exists, return -1.

The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as |x1 - x2| + |y1 - y2|.

Example:

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] have same x or y coordinate as your location. 
The point [2,4] is closest to your location, with a distance of |3-2| + |4-4| = 1.

Clarifying Questions

1. Q: Are the points guaranteed to be unique?
   A: The problem statement doesn’t explicitly mention this, but we’ll assume they are unique for simplicity.

2. Q: What is the maximum number of points in the list?
   A: Leetcode constraints typically make sure that the input size is manageable, often going up to tens of thousands. We’ll use efficient algorithms to handle large inputs.

Strategy

1. Initialization: Start by initializing a variable to keep track of the minimum distance found and the corresponding index of the nearest valid point.
2. Iterate and Check Conditions: Loop through each point and check if either the x or y coordinate matches with our location.
   • If it matches, calculate the Manhattan distance.
   • Update the minimum distance and the corresponding index if this point is closer.
3. Return Result: After checking all points, return the index of the closest point, or -1 if no valid point is found.

Code

def nearestValidPoint(x, y, points):
    nearest_index = -1
    min_distance = float('inf')
    
    for i, (px, py) in enumerate(points):
        if px == x or py == y:
            # Calculate Manhattan distance
            distance = abs(x - px) + abs(y - py)
            if distance < min_distance:
                min_distance = distance
                nearest_index = i
                
    return nearest_index

Time Complexity

• Time Complexity: O(n) where n is the number of points in the list. This is because we iterate through each point once.
• Space Complexity: O(1) because we use only a constant amount of extra space, regardless of the input size.

This approach should efficiently handle even larger inputs within typical constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?