Find Nearest Point That Has the Same X or Y Coordinate

You are given two integers x and y representing your location on a grid, and an array points where points[i] = [ai, bi] represents a point on the grid. A point is valid if it shares the same x-coordinate or the same y-coordinate as your location. Return the index of the valid point with the smallest Manhattan distance from your location. If multiple valid points have the same smallest distance, return the smallest index. If no valid point exists, return -1.

This is LeetCode 1779: Find Nearest Point That Has the Same X or Y Coordinate, and it is a clean example of the linear scan pattern. You walk through the array once, filter as you go, and track the best answer. No sorting, no extra data structures. Just a single loop.

Why this problem matters

This problem drills two fundamental skills at once: filtering elements against a condition and tracking a running minimum with its index. These two operations show up everywhere in array problems. You will see the same structure in "find the closest element that satisfies some property" questions, and it generalizes naturally to problems involving coordinate geometry, Manhattan distance, and geometric filtering.

Manhattan distance itself is a building block worth internalizing. It is the sum of the absolute differences of coordinates: |x1 - x2| + |y1 - y2|. Unlike Euclidean distance, it does not involve square roots, which makes it fast to compute and common in grid-based problems.

The key insight

You do not need to collect valid points into a separate list and then find the minimum. You can do both in a single pass. For each point, check whether it shares your x or y coordinate. If it does, compute the Manhattan distance. If that distance is smaller than the current best (or this is the first valid point), update the best distance and best index.

The tie-breaking rule (smallest index) is handled automatically because you only update the best when the new distance is strictly less than the current best. If a later point ties, you skip it, keeping the earlier index.

The solution

def nearest_valid_point(x: int, y: int, points: list[list[int]]) -> int:
    best_idx = -1
    best_dist = float("inf")

    for i, (px, py) in enumerate(points):
        if px == x or py == y:
            dist = abs(x - px) + abs(y - py)
            if dist < best_dist:
                best_dist = dist
                best_idx = i

    return best_idx

The function starts with best_idx = -1 and best_dist = infinity. These defaults handle the "no valid point" case naturally. If no point passes the validity check, best_idx stays -1 and that is what we return.

The loop uses enumerate to track both the index and the coordinates. For each point, we first check if px == x or py == y. Only then do we compute the Manhattan distance. This avoids unnecessary arithmetic on invalid points. If the computed distance is strictly less than best_dist, we update both the best distance and the best index.

Visual walkthrough

Let's trace through the example with location (3, 4) and points [[1,2],[3,1],[2,4],[2,3],[4,4]]. Watch how the algorithm checks each point, skips invalid ones, and updates the best when it finds a closer valid point.

Notice that points[4] at (4, 4) has the same distance as points[2] at (2, 4), but we keep index 2 because the update only triggers on strictly smaller distances. The earlier index wins ties automatically.

Complexity analysis

Time is O(n) where n is the number of points. We visit each point exactly once, do a constant-time validity check, and a constant-time distance computation for valid points.

Space is O(1). We only store two variables (best_idx and best_dist) regardless of input size. No extra arrays, no hash maps, no sorting.

The building blocks

1. Validity filter

The first building block is the conditional filter: checking whether a point shares a coordinate with your location.

if px == x or py == y:
    pass

This pattern of "check a condition before doing work" shows up in many problems. In Two Sum, you check if the complement exists. In Contains Duplicate, you check if you have seen a value before. Here, you check a geometric property. The structure is the same: filter, then act.

2. Tracking minimum with index

The second building block is maintaining a running minimum along with the index where that minimum was found.

best_idx = -1
best_dist = float("inf")

for i, val in enumerate(items):
    if val < best_dist:
        best_dist = val
        best_idx = i

This is the generic "argmin" pattern. You will use it whenever a problem asks you to return the index (not the value) of the optimal element. The key detail is initializing best_dist to infinity so the first valid comparison always succeeds, and using strict < so ties preserve the earlier index.

Edge cases

• No valid points: every point has a different x and different y from your location. The loop never updates best_idx, so return -1.
• Your location is in the array: if points[i] == [x, y], the distance is 0. Since 0 is less than infinity, this becomes the best immediately. No special handling needed.
• All points are valid: the algorithm still works. It just never skips any point and finds the closest among all of them.
• Single point that is valid: the loop finds it, updates once, and returns that index.
• Multiple points with distance 0: for example, points = [[3,4],[3,4]] with location (3,4). Both have distance 0, but index 0 is returned because the second one does not satisfy dist < best_dist (0 is not less than 0).

From understanding to recall

You have seen how the linear scan combines a validity filter with a running minimum tracker. The logic fits in a few lines and the pattern generalizes to dozens of array problems. But can you write it from memory without looking at the solution?

The details that trip people up are small but important. Do you initialize best_dist to infinity or to zero? Do you use < or <=? Do you compute the distance before or after the validity check? Under interview pressure, these micro-decisions matter.

Spaced repetition makes them automatic. You practice writing the validity filter and the argmin loop from scratch at increasing intervals. After a few rounds, the pattern flows out without hesitation. You see "find the index of the closest valid element" in a problem, and you just write it.

Related posts

• Two Sum - another problem where you scan an array looking for elements that satisfy a condition
• Contains Duplicate - simple array scanning pattern with a condition check
• Koko Eating Bananas - using a scan to find optimal values under a constraint

CodeBricks breaks Find Nearest Point into its validity-filter and minimum-tracker building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an array scanning problem shows up in your interview, you do not think about it. You just write it.