#1779

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Find Nearest Point That Has the Same X or Y Coordinate

Find the nearest point with the same x or y coordinate using Manhattan distance. Return its index or -1 if none exists.

Problem Statement

You are given a location on a Cartesian grid as two integers, x and y. Along with that, you're provided an array of points, each represented as [ai, bi], where each point exists at (ai, bi). A point is considered valid if it shares either the same x-coordinate or the same y-coordinate as your location.

You are tasked with finding the index of the valid point that has the smallest Manhattan distance from your position. If there are multiple valid points with the same distance, return the one with the smallest index. If no valid point exists, return -1. The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as abs(x1 - x2) + abs(y1 - y2).

Examples

Example 1

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

Output: 2

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

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

There are no valid points.

Constraints

1 <= points.length <= 104
points[i].length == 2
1 <= x, y, ai, bi <= 104

Solution Approach

Iterate Through Points

The core solution involves iterating through each point in the given array. For each point, check if its x or y coordinate matches your current location. If so, compute the Manhattan distance from your position and track the smallest one.

Track Closest Point

While iterating, maintain variables to store the index and distance of the closest valid point. Update these values whenever a point with a smaller Manhattan distance is found. In case of ties, keep the point with the smallest index.

Handle Edge Case

If no valid points exist (i.e., no points share either x or y with your current position), return -1. This ensures that your solution works correctly even when no valid points are found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) where n is the number of points, as we must check each point once. The space complexity is O(1) since we only store the minimum distance and index during the iteration.

What Interviewers Usually Probe

Look for efficient iteration through the array with minimal space usage.
Ensure the candidate handles edge cases like no valid points correctly.
Pay attention to how the candidate manages ties in Manhattan distance when multiple points are valid.

Common Pitfalls or Variants

Common pitfalls

Not checking both x and y coordinates to determine if a point is valid.
Failing to account for cases where no valid points exist, which should return -1.
Incorrectly handling ties in Manhattan distance and not returning the point with the smallest index.

Follow-up variants

What if the grid is large, and the points array contains a high number of elements?
How would the solution change if the grid was multidimensional or 3D?
How can this problem be adapted to find the furthest point instead of the nearest?

FAQ

What is the Manhattan distance in this problem?

The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as abs(x1 - x2) + abs(y1 - y2).

How do I handle the case where no valid points exist?

If no valid points are found, return -1 to indicate that no point shares the same x or y coordinate as your current position.

What is the correct approach to handle ties in the Manhattan distance?

If multiple points have the same smallest Manhattan distance, return the point that appears first in the array (i.e., with the smallest index).

How does the 'Find Nearest Point That Has the Same X or Y Coordinate' problem relate to the Array-driven solution strategy?

This problem is solved using an Array-driven strategy by iterating through the array of points and checking each point’s validity based on its coordinates.

What is the time complexity of the solution?

The time complexity of the solution is O(n), where n is the number of points in the array, as we check each point once.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#1776 car fleet ii #1782 count pairs of nodes #1775 equal sum arrays with minimum number of operations