We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Nearest Point That Has the Same X or Y Coordinate

Difficulty: Easy

Problem Description

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.

Key Insights

  • A point is valid if either the x-coordinate or the y-coordinate matches the current location.
  • The Manhattan distance is calculated as abs(x1 - x2) + abs(y1 - y2).
  • We need to track both the smallest distance and the index of the valid point.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will iterate through the list of points and check each point to see if it is valid (i.e., shares the same x or y coordinate). For each valid point, we will compute the Manhattan distance from the current location. We will maintain variables to keep track of the smallest distance found and its corresponding index. If no valid point is found by the end of the list, we will return -1.

Code Solutions

def nearestValidPoint(x: int, y: int, points: List[List[int]]) -> int:
    min_distance = float('inf')  # Initialize minimum distance as infinity
    index_of_nearest = -1  # Initialize index of nearest point as -1

    for index, (a, b) in enumerate(points):
        if a == x or b == y:  # Check if the point is valid
            distance = abs(x - a) + abs(y - b)  # Calculate Manhattan distance
            if distance < min_distance:  # Found a smaller distance
                min_distance = distance
                index_of_nearest = index  # Update the index of nearest point
            elif distance == min_distance:  # Check for smaller index in case of tie
                index_of_nearest = min(index_of_nearest, index)

    return index_of_nearest  # Return the index of the nearest valid point
← Back to All Questions