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.
This approach involves iterating through each point in the array to check if it is valid, i.e., it shares either the x or y coordinate with the given point (x, y). If it is valid, we calculate the Manhattan distance from (x, y) to that point and update the minimum distance and corresponding index. Finally, we return the index of the point with the smallest distance.
In this C solution, we iterate over the array of points using a for loop and check if each point is valid (shares the x or y coordinate). For each valid point, we compute its Manhattan distance, and keep track of the smallest distance and its index.
Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), since we are using a constant amount of extra space.
This approach first filters out all invalid points, leaving only those that share the x or y coordinate with your position. After filtering, it computes the Manhattan distances for these valid points, finds the smallest distance, and returns the corresponding index.
This approach filters invalid points first by directly embedding the condition into the main loop. Valid points are then evaluated for their Manhattan distance, similar to the previous approach.
Time Complexity: O(n), n is the number of points.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Iterative Approach Using Manhattan Distance | Time Complexity: O(n), where n is the number of points. |
| Use of Filter for Valid Points and Finding Minimum | Time Complexity: O(n), n is the number of points. |
| Default Approach | — |
| 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. |
1779. Find Nearest Point That Has the Same X or Y Coordinate (Leetcode Easy) • Programming Live with Larry • 2,389 views views
Watch 9 more video solutions →Practice Find Nearest Point That Has the Same X or Y Coordinate with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor