Find Nearest Point That Has the Same X or Y Coordinate

Find Nearest Point That Has the Same X or Y Coordinate

What is this problem about?

The Find Nearest Point That Has the Same X or Y Coordinate interview question is a grid-based proximity task. You are given your current location $(x, y)$ and an array of points. A point is "valid" if it shares the same x-coordinate or the same y-coordinate as your current location. Your goal is to find the index of the valid point with the smallest Manhattan distance to your location. If there's a tie, you return the smallest index.

Why is this asked in interviews?

Amazon and Google ask the Find Nearest Point coding problem to assess a candidate's basic loop handling and condition-checking skills. It evaluates if you can accurately implement a specific distance formula (Manhattan distance: $|x1 - x2| + |y1 - y2|$) and maintain state (the minimum distance found so far) while iterating through a list. It’s a classic Array interview pattern for entry-level roles.

Algorithmic pattern used

This problem follows the Linear Scan pattern.

1. Initialize: Set minDist to infinity and minIndex to -1.
2. Iterate: Loop through each point in the input array.
3. Filter: Check if point[0] == x OR point[1] == y.
4. Distance Calculation: If valid, calculate the Manhattan distance.
5. Update: If the current distance is strictly less than minDist, update both minDist and minIndex.

Example explanation

Location: (1, 1), Points: [[1, 2], [3, 1], [2, 3]]

1. Point [1, 2]: $x=1$, same as location. Valid. Dist: $|1-1| + |1-2| = 1$. minDist = 1, minIndex = 0.
2. Point [3, 1]: $y=1$, same as location. Valid. Dist: $|1-3| + |1-1| = 2$. Not smaller than 1.
3. Point [2, 3]: No shared coordinates. Invalid. Result: 0.

Common mistakes candidates make

• Ties: Forgetting to return the smallest index in case of a distance tie (usually handled by using a strictly-less < comparison during the update).
• Distance Formula: Using Euclidean distance ($\sqrt{dx^2 + dy^2}$) instead of the requested Manhattan distance.
• Valid Condition: Misinterpreting the "same X or Y" rule and including points that don't satisfy either.

Interview preparation tip

Always clarify the distance metric. While Manhattan distance is common in grid problems, interviewers might swap it for Euclidean or even Chebyshev distance to see if you are paying attention to the specific problem constraints.