Find Nearest Point That Has the Same X or Y Coordinate

Easy

#1628Time: O(N), where N is the number of points. The first loop runs N times, and the second loop runs V times (where V ≤ N). The total time complexity is O(N + V), which simplifies to O(N).Space: O(V), where V is the number of valid points. In the worst-case scenario where all points are valid, the space complexity becomes O(N) to store the valid points and their indices.1 company

Data structures

Array

Companies

DoorDash

Prompt

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] = [a_i, b_i] represents that a point exists at (a_i, b_i). 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 (x₁, y₁) and (x₂, y₂) is abs(x₁ - x₂) + abs(y₁ - y₂).

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 <= 10⁴
points[i].length == 2
1 <= x, y, a_i, b_i <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach separates the problem into two distinct steps. First, it filters the original list of points to create a new list containing only the valid points (those sharing an x or y coordinate). Second, it iterates through this new list of valid points to find the one with the smallest Manhattan distance. This method is straightforward but less optimal due to its use of extra memory and two separate loops.

Algorithm

Initialize two empty lists, one for valid points (validPoints) and one for their original indices (validIndices).
Iterate through the input points array with index i.
For each point p, check if its x-coordinate matches x or its y-coordinate matches y.
If the point is valid, add the point to validPoints and its index i to validIndices.
After the first loop, if validPoints is empty, return -1.
Initialize minDistance to Integer.MAX_VALUE and resultIndex to -1.
Iterate through the validPoints list.
For each valid point, calculate its Manhattan distance to (x, y).
If the calculated distance is less than minDistance, update minDistance to the new distance and resultIndex to the corresponding original index from validIndices.
Return resultIndex.

Walkthrough

In this method, we first iterate through the entire points array to identify all points that are "valid". A point (a, b) is valid if a == x or b == y. We store these valid points and their original indices in separate auxiliary lists.

After populating our lists of valid points and indices, we check if any were found. If not, we return -1. Otherwise, we proceed to a second loop. This loop iterates through our newly created list of valid points. For each valid point, we calculate its Manhattan distance from the reference point (x, y). We keep track of the minimum distance found so far and the original index of the point that yielded this distance. If we find a point with a distance smaller than our current minimum, we update the minimum distance and the result index. Because we process the valid points in the order of their original indices, this naturally handles the tie-breaking rule (smallest index wins).

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int nearestValidPoint(int x, int y, int[][] points) {6        List<int[]> validPoints = new ArrayList<>();7        List<Integer> validIndices = new ArrayList<>();8 9        // First pass: Filter for valid points10        for (int i = 0; i < points.length; i++) {11            if (points[i][0] == x || points[i][1] == y) {12                validPoints.add(points[i]);13                validIndices.add(i);14            }15        }16 17        if (validPoints.isEmpty()) {18            return -1;19        }20 21        int minDistance = Integer.MAX_VALUE;22        int resultIndex = -1;23 24        // Second pass: Find the nearest among valid points25        for (int i = 0; i < validPoints.size(); i++) {26            int[] point = validPoints.get(i);27            int distance = Math.abs(x - point[0]) + Math.abs(y - point[1]);28            if (distance < minDistance) {29                minDistance = distance;30                resultIndex = validIndices.get(i);31            }32        }33        34        return resultIndex;35    }36}

Complexity

Time

O(N), where N is the number of points. The first loop runs N times, and the second loop runs V times (where V ≤ N). The total time complexity is O(N + V), which simplifies to O(N).

Space

O(V), where V is the number of valid points. In the worst-case scenario where all points are valid, the space complexity becomes O(N) to store the valid points and their indices.

Trade-offs

Pros

The logic is separated into clear, distinct steps: filtering and then processing.
It can be easier to reason about for beginners.

Cons

Uses extra space proportional to the number of valid points, which can be up to O(N) in the worst case.
Requires two passes over the data (one on the original array, one on the list of valid points), making it less efficient than a single-pass solution.

This is the most efficient approach, solving the problem in a single pass through the data. It iterates through the points array just once. In each iteration, it checks if the point is valid and, if so, calculates its distance. It maintains a record of the minimum distance found so far and the index of the corresponding point, updating them whenever a closer valid point is found. This avoids the need for extra storage and a second pass.

Algorithm

Initialize minDistance to a very large value (e.g., Integer.MAX_VALUE).
Initialize minIndex to -1, which will be the default return value if no valid point is found.
Iterate through the points array with an index i from 0 to n-1.
For each point p = (px, py):
- Check if the point is valid: if (px == x || py == y).
- If it is valid, calculate its Manhattan distance: distance = abs(x - px) + abs(y - py).
- Compare this distance with minDistance. If distance < minDistance:
  - Update minDistance to this new, smaller distance.
  - Update minIndex to the current index i.
After the loop completes, return minIndex.

Walkthrough

This optimal solution combines the validation, distance calculation, and comparison steps into a single loop. We initialize two variables: minDistance to Integer.MAX_VALUE to track the smallest distance, and minIndex to -1 to store the index of the best point found so far. The -1 initial value for minIndex also handily serves as the return value if no valid points are ever found.

We then iterate through the points array from the first element to the last. For each point, we first check if it shares an x or y coordinate with our location (x, y). If it does, we calculate its Manhattan distance. We then compare this distance with minDistance. If the new distance is strictly smaller, we've found a better candidate point. We update minDistance with this new distance and minIndex with the current point's index.

The strict inequality distance < minDistance is key to handling the tie-breaking rule. If two points have the same minimal distance, the one with the smaller index will be found first. Since we only update when a strictly smaller distance is found, the index of the first-encountered minimal distance point is preserved, satisfying the problem's requirement.

1class Solution {2    public int nearestValidPoint(int x, int y, int[][] points) {3        int minDistance = Integer.MAX_VALUE;4        int minIndex = -1;5 6        for (int i = 0; i < points.length; i++) {7            int px = points[i][0];8            int py = points[i][1];9 10            // Check if the point is valid11            if (px == x || py == y) {12                // Calculate Manhattan distance13                int distance = Math.abs(x - px) + Math.abs(y - py);14 15                // If this point is closer, update the result16                if (distance < minDistance) {17                    minDistance = distance;18                    minIndex = i;19                }20            }21        }22        return minIndex;23    }24}

Complexity

Time

O(N), where N is the number of points in the input array. We perform a single pass through the array, and each operation inside the loop is constant time.

Space

O(1). We only use a constant amount of extra space for variables like `minDistance` and `minIndex`, regardless of the input size.

Trade-offs

Pros

Extremely efficient, with optimal O(N) time complexity.
Space-efficient, using only O(1) extra space.
Solves the problem in a single, elegant pass.
Implicitly handles the tie-breaking rule (smallest index) due to the single forward pass and strict inequality check.

Cons

There are no significant disadvantages to this approach as it is optimal for the given problem and constraints.

Solutions

Solution

1class Solution {2public3  int nearestValidPoint(int x, int y, int[][] points) {4    int ans = -1, mi = 1000000;5    for (int i = 0; i < points.length; ++i) {6      int a = points[i][0], b = points[i][1];7      if (a == x || b == y) {8        int d = Math.abs(a - x) + Math.abs(b - y);9        if (d < mi) {10          mi = d;11          ans = i;12        }13      }14    }15    return ans;16  }17}

1class Solution {2public:3  int nearestValidPoint(int x, int y, vector<vector<int>> &points) {4    int ans = -1, mi = 1e6;5    for (int i = 0; i < points.size(); ++i) {6      int a = points[i][0], b = points[i][1];7      if (a == x || b == y) {8        int d = abs(a - x) + abs(b - y);9        if (d < mi) {10          mi = d;11          ans = i;12        }13      }14    }15    return ans;16  }17};

1class Solution:2    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int: ans, mi = - 1, inf for i, (a, b) in enumerate(points): if a == x or b == y: d = abs(a - x) + abs(b - y) if mi > d: ans, mi = i, d return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem