Leetcode – Find Nearest Point That Has the Same X or Y Coordinate Solution

Spread the love

The problem “Find Nearest Point That Has the Same X or Y Coordinate” on Leetcode is an intriguing algorithmic challenge that can be approached in various ways, using different strategies and Python functionalities. The problem falls under the category of array manipulation and is an excellent exercise to understand the usage of simple data structures and algorithms.

In this comprehensive article, we’ll explore the problem statement, understand multiple approaches to solve it, and analyze their time and space complexities.

Problem Statement

You are given two integers, x and y, which represent your current location on a Cartesian plane. You are also given an array of points where 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:

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

Here, the point at index 4, i.e., (4, 4) is the closest to (3, 4) with a Manhattan distance of 1. No other points are as close.

Approach 1: Brute-force

The most straightforward approach to this problem involves iterating through all the points in the array, calculating the Manhattan distance for each valid point, and then choosing the one with the minimum distance.

Algorithm Steps

  1. Initialize a variable min_distance to float('inf') and min_index to -1.
  2. Loop through each point in the array: a. Check if the point is valid (it has either the same x or y coordinate). b. Calculate the Manhattan distance. c. Update min_distance and min_index accordingly.
  3. Return min_index.

Python Code:

def nearestValidPoint(x, y, points):
    min_distance = float('inf')
    min_index = -1

    for i, (px, py) in enumerate(points):
        if x == px or y == py:
            distance = abs(x - px) + abs(y - py)
            if distance < min_distance:
                min_distance = distance
                min_index = i

    return min_index

Time and Space Complexity

  • Time Complexity: O(n), where n is the number of points.
  • Space Complexity: O(1), as we only use a constant amount of additional space.

Approach 2: Precompute Distances

Another approach is to precompute the distances for each valid point and then find the one with the minimum distance.

Python Code:

def nearestValidPoint(x, y, points):
    distances = [(i, abs(x - px) + abs(y - py)) for i, (px, py) in enumerate(points) if x == px or y == py]
    return min(distances, key=lambda x: (x[1], x[0]), default=(-1,))[0]

Time and Space Complexity

  • Time Complexity: O(n)
  • Space Complexity: O(k), where k is the number of valid points.

Approach 3: Using min( ) function with Conditions

We can use Python’s built-in min() function with conditional statements to make the code more concise.

Python Code:

def nearestValidPoint(x, y, points):
    return min((i for i, (px, py) in enumerate(points) if x == px or y == py), key=lambda i: abs(x - points[i][0]) + abs(y - points[i][1]), default=-1)

Time and Space Complexity

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

Conclusion

The “Find Nearest Point That Has the Same X or Y Coordinate” problem is a straightforward yet versatile problem, ideal for mastering array manipulation techniques and getting familiar with the concept of Manhattan distance. Although the problem is simple, it offers a nice introduction to different Python techniques and methods for problem-solving.

Leave a Reply