Watch 10 video solutions for Find Nearest Point That Has the Same X or Y Coordinate, a easy level problem involving Array. This walkthrough by Programming Live with Larry has 2,389 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [ai, bi] represents that a point exists at (ai, bi). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.
Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.
The Manhattan distance between two points (x1, y1) and (x2, y2) is abs(x1 - x2) + abs(y1 - y2).
Example 1:
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] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.
Example 2:
Input: x = 3, y = 4, points = [[3,4]] Output: 0 Explanation: The answer is allowed to be on the same location as your current location.
Example 3:
Input: x = 3, y = 4, points = [[2,3]] Output: -1 Explanation: There are no valid points.
Constraints:
1 <= points.length <= 104points[i].length == 21 <= x, y, ai, bi <= 104Problem Overview: You are given your current location (x, y) and a list of points. A point is considered valid if it shares the same x coordinate or the same y coordinate. Among all valid points, return the index of the point with the smallest Manhattan distance from your location. If multiple points have the same distance, return the smallest index.
Approach 1: Iterative Approach Using Manhattan Distance (O(n) time, O(1) space)
Scan the array once and evaluate each point. A point is valid if px == x or py == y. For valid points, compute the Manhattan distance using |px - x| + |py - y|. Track the smallest distance seen so far along with its index. Because the scan proceeds from left to right, the first occurrence naturally preserves the smallest index when distances tie. This approach uses a simple loop and constant extra memory, making it optimal for problems involving array traversal.
Approach 2: Filter Valid Points and Find Minimum (O(n) time, O(n) space)
First filter the list to keep only points that share the same x or y coordinate. For each valid point, compute the Manhattan distance and store a tuple of (distance, index). After filtering, select the tuple with the smallest distance (and smallest index in case of ties). Many languages allow concise implementations using functional utilities such as filter, list comprehensions, or streams. This version separates validation from distance computation, which can improve readability when working with coordinate-based array problems or simple geometry logic.
Recommended for interviews: The single-pass iterative solution is what interviewers expect. It demonstrates you understand Manhattan distance and can solve the problem in one linear scan with constant space. The filtering approach is also linear but introduces extra memory and abstraction layers. Showing the direct scan first proves you can reason about constraints and implement an optimal O(n) solution quickly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Manhattan Distance Scan | O(n) | O(1) | Best general solution. Single pass through the array with minimal memory. |
| Filter Valid Points Then Compute Minimum | O(n) | O(n) | Useful for cleaner functional-style code or when separating validation and computation logic. |