Problem Description

You are given your current position (x, y) on a Cartesian grid and an array points where each element points[i] = [ai, bi] represents a point at coordinates (ai, bi).

A point is considered valid if it shares either the same x-coordinate or the same y-coordinate with your current location. In other words, a point (ai, bi) is valid if either ai == x or bi == y.

Your task is to find the valid point that has the smallest Manhattan distance from your current location (x, y). The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as abs(x1 - x2) + abs(y1 - y2).

The function should return:

• The index (0-indexed) of the valid point with the smallest Manhattan distance
• If multiple valid points have the same smallest distance, return the one with the smallest index
• If no valid points exist, return -1

For example, if you are at position (3, 4) and have points [[1, 2], [3, 1], [2, 4], [3, 5]]:

• Point at index 0 [1, 2] is not valid (neither x nor y coordinate matches)
• Point at index 1 [3, 1] is valid (x-coordinate matches) with distance = |3-3| + |1-4| = 3
• Point at index 2 [2, 4] is valid (y-coordinate matches) with distance = |2-3| + |4-4| = 1
• Point at index 3 [3, 5] is valid (x-coordinate matches) with distance = |3-3| + |5-4| = 1

Since points at indices 2 and 3 both have the minimum distance of 1, we return 2 (the smaller index).

Intuition

The key insight is that we need to check every point in the array to determine if it's valid, and among the valid points, track which one has the minimum Manhattan distance.

Since a valid point must share either the x-coordinate or y-coordinate with our current position, we can filter points by checking if a == x or b == y. For points that don't meet this condition, we can immediately skip them.

For each valid point, we calculate its Manhattan distance from our position. Since one coordinate already matches (either x or y), the Manhattan distance simplifies:

• If a == x, then the distance is just abs(b - y)
• If b == y, then the distance is just abs(a - x)
• If both coordinates match (the point is at our exact location), the distance is 0

We need to keep track of two things as we iterate through the points:

1. The minimum distance found so far
2. The index of the point with that minimum distance

The natural approach is a single pass through the array. As we encounter each valid point, we compare its distance with our current minimum. If we find a smaller distance, we update both the minimum distance and the answer index. Since we're iterating from index 0 onwards, we naturally handle the tie-breaking rule - when multiple points have the same minimum distance, we automatically keep the first one (smallest index) we encountered.

Initializing the minimum distance to infinity ensures that the first valid point we find will become our initial candidate, and initializing the answer to -1 handles the case where no valid points exist.

Solution Approach

The solution uses a simple linear scan approach with tracking variables to find the nearest valid point.

Implementation Steps:

1. Initialize tracking variables:

   • ans = -1: Stores the index of the nearest valid point (initialized to -1 for the case when no valid point exists)
   • mi = inf: Stores the minimum Manhattan distance found so far (initialized to infinity to ensure any valid distance will be smaller)

2. Iterate through all points with their indices:

   for i, (a, b) in enumerate(points):

   • Use enumerate() to get both the index i and the coordinates (a, b) of each point

3. Check if the current point is valid:

   if a == x or b == y:

   • A point is valid if it shares either the x-coordinate (a == x) or y-coordinate (b == y) with our position

4. Calculate Manhattan distance for valid points:

   d = abs(a - x) + abs(b - y)

   • Even though one coordinate matches, we use the full Manhattan distance formula for simplicity
   • When a == x, this becomes abs(b - y)
   • When b == y, this becomes abs(a - x)

5. Update the minimum distance and answer:

   if mi > d:
       ans, mi = i, d

   • Only update when we find a strictly smaller distance
   • This ensures we keep the smallest index in case of ties (since we process points in order)

6. Return the result:

   • After checking all points, return ans
   • This will be -1 if no valid points were found, or the index of the nearest valid point otherwise

Time Complexity: O(n) where n is the number of points, as we make a single pass through the array.

Space Complexity: O(1) as we only use a constant amount of extra space for tracking variables.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works step by step.

Given:

• Current position: (x, y) = (3, 4)
• Points array: [[1, 2], [3, 1], [2, 4], [3, 5], [5, 4]]

Initialize tracking variables:

• ans = -1 (no valid point found yet)
• mi = infinity (no minimum distance yet)

Step 1: Check point [1, 2] at index 0

• Is it valid? Check if 1 == 3 (no) or 2 == 4 (no)
• Not valid, skip this point
• ans = -1, mi = infinity

Step 2: Check point [3, 1] at index 1

• Is it valid? Check if 3 == 3 (yes!)
• Valid! Calculate distance: |3-3| + |1-4| = 0 + 3 = 3
• Is 3 < infinity? Yes, update!
• ans = 1, mi = 3

Step 3: Check point [2, 4] at index 2

• Is it valid? Check if 2 == 3 (no) or 4 == 4 (yes!)
• Valid! Calculate distance: |2-3| + |4-4| = 1 + 0 = 1
• Is 1 < 3? Yes, update!
• ans = 2, mi = 1

Step 4: Check point [3, 5] at index 3

• Is it valid? Check if 3 == 3 (yes!)
• Valid! Calculate distance: |3-3| + |5-4| = 0 + 1 = 1
• Is 1 < 1? No, don't update (keeps smaller index for ties)
• ans = 2, mi = 1

Step 5: Check point [5, 4] at index 4

• Is it valid? Check if 5 == 3 (no) or 4 == 4 (yes!)
• Valid! Calculate distance: |5-3| + |4-4| = 2 + 0 = 2
• Is 2 < 1? No, don't update
• ans = 2, mi = 1

Result: Return ans = 2

The point at index 2 [2, 4] is the nearest valid point with a Manhattan distance of 1. Even though the point at index 3 also has distance 1, we return index 2 because it comes first.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of points in the input list. The algorithm iterates through the list of points exactly once using a single for loop. Within each iteration, all operations (checking equality conditions, calculating Manhattan distance, and comparing/updating variables) are performed in constant time O(1). Therefore, the overall time complexity is linear.

Space Complexity: O(1) constant space. The algorithm only uses a fixed amount of extra space regardless of the input size. The variables used are:

• ans: stores the index of the nearest valid point
• mi: stores the minimum distance found so far
• i, a, b: loop variables for iteration

Since these variables don't scale with the input size and no additional data structures are created, the space complexity remains constant.

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

Common Pitfalls

1. Incorrectly Handling Ties in Distance

Pitfall: A common mistake is using <= instead of < when comparing distances, which would incorrectly update the answer to a higher index when multiple points have the same minimum distance.

# INCORRECT - This will return the last index among tied distances
if distance <= min_distance:  # Wrong!
    nearest_index = index
    min_distance = distance

Solution: Use strict inequality (<) to ensure we only update when finding a strictly smaller distance:

# CORRECT - This keeps the first (smallest) index among tied distances
if distance < min_distance:
    nearest_index = index
    min_distance = distance

2. Forgetting to Check Point Validity

Pitfall: Calculating distances for all points without first checking if they're valid (sharing x or y coordinate):

# INCORRECT - Considers all points, not just valid ones
for index, (point_x, point_y) in enumerate(points):
    distance = abs(point_x - x) + abs(point_y - y)
    if distance < min_distance:
        nearest_index = index
        min_distance = distance

Solution: Always check validity before calculating distance:

# CORRECT - Only processes valid points
for index, (point_x, point_y) in enumerate(points):
    if point_x == x or point_y == y:  # Validity check first
        distance = abs(point_x - x) + abs(point_y - y)
        if distance < min_distance:
            nearest_index = index
            min_distance = distance

3. Using AND Instead of OR for Validity Check

Pitfall: Misunderstanding the problem and checking if both coordinates match:

# INCORRECT - Too restrictive, only accepts points at exact position
if point_x == x and point_y == y:  # Wrong logic!
    # This would only match points at the exact same position

Solution: Use OR to check if either coordinate matches:

# CORRECT - Accepts points sharing either x OR y coordinate
if point_x == x or point_y == y:
    # Process valid point

4. Not Initializing the Minimum Distance Properly

Pitfall: Initializing min_distance to 0 or a small fixed value:

# INCORRECT - May miss valid points with distance > 0
min_distance = 0  # Wrong initialization!

Solution: Initialize to infinity to ensure any valid distance will be smaller:

# CORRECT - Ensures first valid point will be considered
min_distance = float('inf')