Introduction

In this blog post, we will explore how to solve the LeetCode problem "1779" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's the solution:

• Identify Valid Points: Iterate through the points array and check if each point shares the same x-coordinate or y-coordinate with the given location (x, y).
• Calculate Manhattan Distance: For each valid point, compute the Manhattan distance to the current location.

• Find Minimum Distance and Index: Keep track of the minimum Manhattan distance found so far and the index of the corresponding point. If a new valid point has a smaller distance, update the minimum distance and index. If the distance is the same, choose the point with the smaller index.

• Runtime Complexity: O(n), where n is the number of points. Storage Complexity: O(1).

Code

    def nearestValidPoint(x: int, y: int, points: list[list[int]]) -> int:
    """
    Finds the index of the nearest valid point in a list of points.

    Args:
        x: The x-coordinate of the current location.
        y: The y-coordinate of the current location.
        points: A list of points, where each point is a list [ai, bi].

    Returns:
        The index of the nearest valid point (0-indexed). Returns -1 if no valid points are found.
    """

    min_dist = float('inf')
    min_index = -1

    for i, point in enumerate(points):
        a, b = point
        if a == x or b == y:
            dist = abs(x - a) + abs(y - b)
            if dist < min_dist:
                min_dist = dist
                min_index = i
            elif dist == min_dist and i < min_index:
                min_index = i

    return min_index