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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Nearest Point That Has the Same X or Y Coordinate

Number: 1888

Difficulty: Easy

Paid? No

Companies: DoorDash, Amazon

Problem Description

Given a current location (x, y) and an array of points, find the index of a valid point that is the nearest in Manhattan distance. A point is considered valid if it shares the same x-coordinate or the same y-coordinate as (x, y). If multiple valid points have the same minimum Manhattan distance, return the one with the smallest index. If no valid point exists, return -1.

Key Insights

  • A valid point must have either the same x-coordinate or the same y-coordinate as the current location.
  • The Manhattan distance between two points (x1, y1) and (x2, y2) is computed as abs(x1 - x2) + abs(y1 - y2).
  • Iterating over the points array and checking the validity condition allows you to update the smallest distance and corresponding index.
  • Edge cases include when no valid points exist (return -1) and when the valid point is at the same location as (x, y).

Space and Time Complexity

Time Complexity: O(n) where n is the number of points in the list, since a single pass is used. Space Complexity: O(1) since only a few variables are used regardless of the input size.

Solution

We traverse the entire points array while checking each point for validity (same x or y coordinate). For valid points, we compute the Manhattan distance to (x, y) and track the minimum distance found so far along with its index. Finally, we return the index of the valid point with the smallest Manhattan distance; if none are valid, we return -1. The solution uses a simple iterative approach and basic arithmetic operations.

Code Solutions

# Python implementation

def nearestValidPoint(x, y, points):
    # Initialize the minimum distance to a large number and result index to -1
    min_distance = float('inf')
    result_index = -1
    
    # Iterate over each point, tracking the index
    for index, (a, b) in enumerate(points):
        # Check if the point is valid: same x or same y as the current location
        if a == x or b == y:
            # Calculate the Manhattan distance to the current location
            distance = abs(x - a) + abs(y - b)
            # If a new smaller distance is found, or same distance with a lower index, update results
            if distance < min_distance:
                min_distance = distance
                result_index = index
    return result_index

# Example usage:
# print(nearestValidPoint(3, 4, [[1,2],[3,1],[2,4],[2,3],[4,4]]))
← Back to All Questions