Find Nearest Point That Has the Same X or Y Coordinate

Easy

Asked by:

47 views

Topics:

Arrays

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] = [a_i, b_i] represents that a point exists at (a_i, b_i). 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 (x₁, y₁) and (x₂, y₂) is abs(x₁ - x₂) + abs(y₁ - y₂).

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 <= 10⁴
points[i].length == 2
1 <= x, y, a_i, b_i <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of x, y, ai, and bi? For example, what is the maximum possible value, and can they be negative?
If multiple points are equidistant and satisfy the condition of sharing either the same x or y coordinate, should I return the point with the smallest index?
If the input list of points is empty or if no point shares either the same x or y coordinate with the location (x, y), what value should I return?
What is the maximum possible length of the 'points' array?
Should I consider the case where the input 'points' array contains null or invalid point entries (e.g., a point with a null x or y coordinate)?

Brute Force Solution

Approach

The brute force approach means we will look at every single point to see if it shares either the same x or y coordinate as our starting point. We'll calculate the distance for each of these valid points and return the closest one.

Here's how the algorithm would work step-by-step:

Go through each point in the given list of points, one by one.
For each point, check if its x coordinate is the same as the x coordinate of our starting point, or if its y coordinate is the same as the y coordinate of our starting point.
If neither coordinate is the same, then skip this point and move to the next one.
If one of the coordinates is the same, calculate the distance between this point and our starting point.
Keep track of the shortest distance found so far, and the point that corresponds to that distance.
After checking all the points, return the point that had the shortest distance.

Code Implementation

def find_nearest_point_brute_force(starting_point, points):
    shortest_distance = float('inf')
    nearest_point_index = -1

    # Iterate through each point in the list
    for index, current_point in enumerate(points):

        # Check if either x or y coordinate is the same
        if (current_point[0] == starting_point[0] or\
            current_point[1] == starting_point[1]):

            # Calculate Manhattan distance
            distance = abs(current_point[0] - starting_point[0]) +\
                       abs(current_point[1] - starting_point[1])

            # Update shortest distance if necessary
            if distance < shortest_distance:

                # We found a new nearest point
                shortest_distance = distance
                nearest_point_index = index

    return nearest_point_index

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n points in the input list once. For each point, it performs a constant number of operations: checking if the x or y coordinate matches the starting point's coordinates, and calculating the distance if there's a match. Since these operations take constant time, the overall time complexity is determined by the single loop over the n points. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a few variables to store the shortest distance found so far and the index of the closest point. These variables consume a constant amount of space regardless of the number of points (N). No additional data structures like lists or hash maps are created to store intermediate results. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The key idea is to only consider points that share either an x or y coordinate with our starting point and then find the closest one among them. We can avoid unnecessary calculations by ignoring points that aren't aligned along the same horizontal or vertical line. This significantly reduces the number of distances we need to calculate.

Here's how the algorithm would work step-by-step:

First, go through the entire list of points and identify which ones have either the same x-coordinate or the same y-coordinate as your starting point. These are your candidates for the nearest point.
If there are no candidate points found in the previous step, then return -1 meaning there is no solution.
Next, for each candidate, calculate the 'Manhattan distance', which is the sum of the differences in x and y coordinates between the candidate point and the starting point.
Keep track of the smallest distance you've found so far and the index of the point associated with that distance.
After checking all the valid candidates, return the index of the point that had the smallest Manhattan distance. This will be the index of the nearest point that shares either an x or y coordinate.

Code Implementation

def find_nearest_valid_point(
        x_coordinate, y_coordinate, points):
    smallest_distance = float('inf')
    nearest_point_index = -1

    # Iterate through each point to find valid candidates
    for index, (point_x, point_y) in enumerate(points):
        if x_coordinate == point_x or y_coordinate == point_y:
            # Calculate Manhattan distance for valid points

            manhattan_distance = abs(x_coordinate - point_x) + \
                abs(y_coordinate - point_y)

            # Update nearest point if current distance is smaller
            if manhattan_distance < smallest_distance:
                smallest_distance = manhattan_distance
                nearest_point_index = index

    return nearest_point_index

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of points once to identify candidate points that share either the x or y coordinate with the starting point. After identifying candidate points, it iterates through these candidates to calculate Manhattan distances. In the worst case, all points share either the x or y coordinate, resulting in a second iteration of potentially n points. Therefore, the overall time complexity is dominated by these two linear iterations, which sums to O(2n), simplifying to O(n).

Space Complexity

O(N) – The algorithm iterates through the input list of points (of size N) to identify candidate points that share the same x or y coordinate with the starting point. In the worst-case scenario, all N points could be candidates, requiring storage of their indices. The algorithm also uses a few constant space variables to store the minimum distance found so far and the index associated with that distance; these do not depend on the input size. Therefore, the space complexity is dominated by the potential storage of up to N indices for candidate points, resulting in O(N) auxiliary space.

Edge Cases

Case	How to Handle
Empty points array	Return -1 immediately because no valid point can exist if the points array is empty.
Null points array	Return -1 immediately, treating null input as no valid points.
Points array containing null points	Skip the null point during iteration to prevent NullPointerException and continue to process valid points.
Very large number of points in the points array (scalability)	Ensure the solution iterates efficiently to avoid timeouts with large input sizes; consider using appropriate data structures like priority queues if necessary.
Points with the same X and Y coordinate as the location	Include these points in the distance calculation and index comparison to ensure the absolute nearest by Manhattan Distance is correctly identified.
Multiple points with the same minimum Manhattan distance	Maintain the smallest index among points with equal minimum Manhattan distance.
Integer overflow in Manhattan distance calculation	Consider using long type for distance calculation to prevent potential overflows if the coordinates are large.
All points are equidistant from the location and share X or Y coordinate	The solution should select the point with the smallest index among all points with the minimum Manhattan distance.

Empty points array

How to Handle:

Return -1 immediately because no valid point can exist if the points array is empty.

Null points array

How to Handle:

Return -1 immediately, treating null input as no valid points.

Points array containing null points

How to Handle:

Skip the null point during iteration to prevent NullPointerException and continue to process valid points.

Very large number of points in the points array (scalability)

How to Handle:

Ensure the solution iterates efficiently to avoid timeouts with large input sizes; consider using appropriate data structures like priority queues if necessary.

Points with the same X and Y coordinate as the location

How to Handle:

Include these points in the distance calculation and index comparison to ensure the absolute nearest by Manhattan Distance is correctly identified.

Multiple points with the same minimum Manhattan distance

How to Handle:

Maintain the smallest index among points with equal minimum Manhattan distance.

Integer overflow in Manhattan distance calculation

How to Handle:

Consider using long type for distance calculation to prevent potential overflows if the coordinates are large.

All points are equidistant from the location and share X or Y coordinate

How to Handle:

The solution should select the point with the smallest index among all points with the minimum Manhattan distance.