# Find Nearest Point That Has the Same X or Y Coordinate
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate)
Canonical: https://scaleengineer.com/dsa/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate
**Data structures:** Array
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## Problem
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 <= 104`
* `points[i].length == 2`
* `1 <= x, y, ai, bi <= 104`

# Approaches
## Two-Pass Approach with Extra Space
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.
**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.
**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.
### Explanation
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).

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        List<int[]> validPoints = new ArrayList<>();
        List<Integer> validIndices = new ArrayList<>();

        // First pass: Filter for valid points
        for (int i = 0; i < points.length; i++) {
            if (points[i][0] == x || points[i][1] == y) {
                validPoints.add(points[i]);
                validIndices.add(i);
            }
        }

        if (validPoints.isEmpty()) {
            return -1;
        }

        int minDistance = Integer.MAX_VALUE;
        int resultIndex = -1;

        // Second pass: Find the nearest among valid points
        for (int i = 0; i < validPoints.size(); i++) {
            int[] point = validPoints.get(i);
            int distance = Math.abs(x - point[0]) + Math.abs(y - point[1]);
            if (distance < minDistance) {
                minDistance = distance;
                resultIndex = validIndices.get(i);
            }
        }
        
        return resultIndex;
    }
}
```
### 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`.

## Single-Pass Linear Scan
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        int minDistance = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < points.length; i++) {
            int px = points[i][0];
            int py = points[i][1];

            // Check if the point is valid
            if (px == x || py == y) {
                // Calculate Manhattan distance
                int distance = Math.abs(x - px) + Math.abs(y - py);

                // If this point is closer, update the result
                if (distance < minDistance) {
                    minDistance = distance;
                    minIndex = i;
                }
            }
        }
        return minIndex;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int nearestValidPoint(int x, int y, int[][] points) {
    int ans = -1, mi = 1000000;
    for (int i = 0; i < points.length; ++i) {
      int a = points[i][0], b = points[i][1];
      if (a == x || b == y) {
        int d = Math.abs(a - x) + Math.abs(b - y);
        if (d < mi) {
          mi = d;
          ans = i;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int nearestValidPoint(int x, int y, vector<vector<int>> &points) {
    int ans = -1, mi = 1e6;
    for (int i = 0; i < points.size(); ++i) {
      int a = points[i][0], b = points[i][1];
      if (a == x || b == y) {
        int d = abs(a - x) + abs(b - y);
        if (d < mi) {
          mi = d;
          ans = i;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```