{x}
blog image

Find Nearest Point That Has the Same X or Y Coordinate

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

Solution Explanation

The problem asks to find the nearest valid point to a given point (x, y) from a list of points. A valid point is one that shares the same x-coordinate or y-coordinate with (x, y). The distance is measured using Manhattan distance. If multiple valid points have the same minimum Manhattan distance, the point with the smallest index should be returned.

The solution iterates through the list of points. For each point, it checks if it's valid (shares the same x or y coordinate). If it is, it calculates the Manhattan distance to the given point (x, y). It keeps track of the minimum distance found so far and the index of the corresponding point. The algorithm prioritizes points with a smaller index in case of ties in Manhattan distance.

Time Complexity Analysis

The solution iterates through the points array once. The operations inside the loop (checking validity, calculating Manhattan distance, and comparison) are all constant time operations. Therefore, the overall time complexity is O(n), where n is the number of points in the input array.

Space Complexity Analysis

The solution uses a constant amount of extra space to store variables like ans, mi, a, b, and d. The space used does not depend on the input size. Therefore, the space complexity is O(1).

Code Explanation (Python)

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        ans, mi = -1, inf  # Initialize the answer to -1 (no valid point) and minimum distance to infinity
        for i, (a, b) in enumerate(points): # Iterate through points with index i and coordinates (a,b)
            if a == x or b == y: # Check if the point is valid
                d = abs(a - x) + abs(b - y) # Calculate Manhattan distance
                if mi > d: # If current distance is less than minimum distance
                    ans, mi = i, d # Update the answer and minimum distance
        return ans # Return the index of the nearest valid point

The other language implementations follow the same logic, differing only in syntax and library functions used. The core algorithm remains consistent across all languages.