LeetCode 1779 - Find Nearest Point That Has the Same X or Y Coordinate

The problem gives your current position on a 2D Cartesian grid as (x, y) and a list of other points. Each point is represented as [ai, bi].

leetcodeeasyarray

LeetCode Problem 1779

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives your current position on a 2D Cartesian grid as (x, y) and a list of other points. Each point is represented as [ai, bi].

A point is considered valid if it shares either:

  • the same x-coordinate as your location, meaning ai == x
  • the same y-coordinate as your location, meaning bi == y

Among all valid points, we must find the one with the smallest Manhattan distance from (x, y).

The Manhattan distance between two points is:

$|x_1-x_2|+|y_1-y_2|$

In this problem, the distance from (x, y) to (ai, bi) becomes:

$|x-a_i|+|y-b_i|$

If multiple valid points have the same minimum distance, we return the one with the smallest index in the points array.

If no point shares either coordinate with (x, y), we return -1.

The constraints are relatively small:

  • points.length <= 10^4
  • coordinates are at most 10^4

These limits immediately suggest that a simple linear scan through all points is completely acceptable. Even an O(n) or O(n log n) solution would be fast enough, but there is no need for anything more complicated than a single pass.

There are several important edge cases to keep in mind:

  • There may be no valid points at all.
  • Multiple points can have the same minimum distance.
  • A valid point can be exactly the same as the current location, producing distance 0.
  • The first valid point encountered may not be the closest one.
  • Later points may tie the minimum distance, but ties must preserve the smaller index.

Because the problem explicitly asks for the smallest index when distances tie, we must update the answer only when we find a strictly smaller distance.

Approaches

Brute Force Approach

The brute-force approach is to examine every point in the array one by one.

For each point:

  1. Check whether it is valid, meaning it shares the same x-coordinate or y-coordinate.
  2. If valid, compute its Manhattan distance.
  3. Compare this distance with the smallest distance seen so far.
  4. Update the answer if the current point is better.

This approach is correct because every possible candidate is inspected exactly once, so no valid point can be missed.

Technically, this already runs in linear time, which is efficient enough for the constraints. There is no slower naive solution that needs optimization here. The brute-force method is effectively the optimal method.

Key Insight

The key observation is that validity depends only on a simple coordinate comparison:

  • ai == x
  • or bi == y

There is no need for sorting, preprocessing, or advanced data structures.

Since we only need the minimum Manhattan distance among valid points, a single pass through the array is sufficient. During this scan, we maintain:

  • the best distance found so far
  • the index of the corresponding point

Because Manhattan distance can be computed in constant time, the entire algorithm works in linear time with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Scan every point and compute distances for valid points
Optimal O(n) O(1) Same linear scan, already optimal for the problem constraints

Algorithm Walkthrough

  1. Initialize two variables:
  • best_distance as infinity
  • best_index as -1

These variables track the closest valid point discovered so far. 2. Iterate through the points array using both the index and the point coordinates. 3. For each point (px, py), check whether it is valid:

  • px == x
  • or py == y

If neither condition is true, skip the point immediately. 4. For a valid point, compute the Manhattan distance:

$|x-p_x|+|y-p_y|$ 5. Compare this distance with best_distance.

  • If the new distance is smaller, update:

  • best_distance

  • best_index

  1. Do not update the answer when distances are equal.

This automatically preserves the smallest index because the earlier point remains stored. 7. After processing all points, return best_index.

Why it works

The algorithm checks every point exactly once and evaluates all valid candidates. Since best_distance always stores the minimum distance encountered so far, the final answer must be the closest valid point. By updating only on strictly smaller distances, ties automatically keep the earliest index, satisfying the problem requirements.

Python Solution

from typing import List

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        best_distance = float("inf")
        best_index = -1

        for index, (px, py) in enumerate(points):
            if px == x or py == y:
                distance = abs(x - px) + abs(y - py)

                if distance < best_distance:
                    best_distance = distance
                    best_index = index

        return best_index

The implementation follows the algorithm directly.

The variables best_distance and best_index maintain the current optimal answer. best_distance starts at infinity so that the first valid point automatically becomes the current best candidate.

The loop uses enumerate so we can access both the point and its index at the same time. For every point, we first verify whether it shares either coordinate with the current location.

If the point is valid, we compute the Manhattan distance using absolute differences. Whenever the computed distance is strictly smaller than the current best distance, we update both tracking variables.

Finally, after all points have been processed, we return best_index. If no valid point was ever found, the value remains -1.

Go Solution

func nearestValidPoint(x int, y int, points [][]int) int {
	bestDistance := int(^uint(0) >> 1)
	bestIndex := -1

	for i, point := range points {
		px := point[0]
		py := point[1]

		if px == x || py == y {
			distance := abs(x-px) + abs(y-py)

			if distance < bestDistance {
				bestDistance = distance
				bestIndex = i
			}
		}
	}

	return bestIndex
}

func abs(value int) int {
	if value < 0 {
		return -value
	}

	return value
}

The Go implementation mirrors the Python solution closely.

Since Go does not provide a built-in integer infinity value, the code initializes bestDistance using the maximum possible integer value.

Go also lacks a built-in abs function for integers, so a small helper function is implemented manually.

The rest of the solution uses a standard range loop over the slice of points and updates the best candidate exactly the same way as the Python version.

Worked Examples

Example 1

Input:
x = 3
y = 4
points = [[1,2],[3,1],[2,4],[2,3],[4,4]]

Initial state:

Variable Value
best_distance inf
best_index -1

Iteration details:

Index Point Valid? Distance Action
0 [1,2] No - Skip
1 [3,1] Yes 3 Update answer
2 [2,4] Yes 1 Better distance, update
3 [2,3] No - Skip
4 [4,4] Yes 1 Tie, keep smaller index

Final result:

best_index = 2

Example 2

Input:
x = 3
y = 4
points = [[3,4]]
Index Point Valid? Distance Action
0 [3,4] Yes 0 Update answer

Final result:

0

The point is exactly the same as the current location, so the Manhattan distance is 0.

Example 3

Input:
x = 3
y = 4
points = [[2,3]]
Index Point Valid? Action
0 [2,3] No Skip

No valid points are found, so the answer remains:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each point is visited exactly once
Space O(1) Only a few variables are used

The algorithm performs a single linear scan through the input array. Each iteration does only constant-time work, consisting of coordinate comparisons and a Manhattan distance calculation.

No auxiliary data structures proportional to input size are allocated, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        best_distance = float("inf")
        best_index = -1

        for index, (px, py) in enumerate(points):
            if px == x or py == y:
                distance = abs(x - px) + abs(y - py)

                if distance < best_distance:
                    best_distance = distance
                    best_index = index

        return best_index

solution = Solution()

assert solution.nearestValidPoint(
    3, 4, [[1, 2], [3, 1], [2, 4], [2, 3], [4, 4]]
) == 2  # standard example with tie

assert solution.nearestValidPoint(
    3, 4, [[3, 4]]
) == 0  # same point as current location

assert solution.nearestValidPoint(
    3, 4, [[2, 3]]
) == -1  # no valid points

assert solution.nearestValidPoint(
    1, 1, [[1, 2], [1, 3], [1, 0]]
) == 0  # first valid point is closest

assert solution.nearestValidPoint(
    5, 5, [[5, 6], [6, 5], [5, 4]]
) == 0  # multiple equal distances, smallest index wins

assert solution.nearestValidPoint(
    2, 8, [[2, 10], [3, 8], [2, 7]]
) == 2  # later point has smaller distance

assert solution.nearestValidPoint(
    7, 7, [[1, 1], [2, 2], [3, 3]]
) == -1  # completely invalid set

assert solution.nearestValidPoint(
    4, 4, [[4, 5], [4, 3], [5, 4], [3, 4]]
) == 0  # all valid, first minimum retained

assert solution.nearestValidPoint(
    10, 10, [[10, 10], [10, 11], [11, 10]]
) == 0  # zero distance should dominate
Test Why
Standard example with tie Verifies tie-breaking by smallest index
Same point as current location Confirms distance 0 is handled correctly
No valid points Ensures -1 is returned properly
First valid point closest Verifies normal minimum selection
Multiple equal distances Confirms tie handling
Later point closer Ensures updates happen correctly
Completely invalid set Tests absence of valid coordinates
All points valid Verifies repeated comparisons
Zero distance case Confirms optimal distance handling

Edge Cases

No Valid Points

A common bug is forgetting to handle the situation where no point shares either coordinate with the current location. In that case, the algorithm should return -1.

This implementation handles the case naturally because best_index starts at -1 and changes only when a valid point is found.

Multiple Points With the Same Distance

Another subtle issue occurs when multiple valid points have identical Manhattan distances. The problem requires returning the smallest index.

The implementation avoids accidental overwriting by updating the answer only when the new distance is strictly smaller than the current best distance. Equal distances are ignored, preserving the earlier index.

Point Identical to Current Location

A point may exactly equal (x, y). Its Manhattan distance is:

$|x-x|+|y-y|=0$

Distance 0 is the smallest possible distance, so this point should immediately become the best answer.

The implementation correctly computes this value and updates the answer as expected.