Leetcode 1779. Find Nearest Point That Has the Same X or Y Coordinate

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.

Programming Skills I Easy

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.

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

• 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

• 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

• There are no valid points.

Constraints:

• 1 <= points.length <= 10^4
• points[i].length == 2
• 1 <= x, y, ai, bi <= 10^4

Solution

class Solution:
    # Iteration
    # Time Complexity: BigO(N)
    # Space Complexity: BigO(1)
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        count, smallest = 0, 10000
        for i in range(len(points)):
            manhattan = abs(x - points[i][0]) + abs(y - points[i][1])
            if points[i][0] == x and points[i][1] == y:
                return i
            elif (points[i][0] == x or points[i][1] == y) and smallest >= manhattan:
                if smallest == manhattan:
                    count += 1
                else:
                    smallest = manhattan
                    index = i
                    count = 1

        return index if count >= 1 else -1

/**
 * Iteration
 * Time Complexity: BigO(N)
 * Space Complexity: BigO(1)
 */
function nearestValidPoint(x: number, y: number, points: number[][]): number {
  let smallest: number | undefined = undefined;
  let index: number = -1;
  let count = 0;
  for (let i = 0; i < points.length; i++) {
    let manhattan = Math.abs(x - points[i][0]) + Math.abs(y - points[i][1]);
    if (points[i][0] == x && points[i][1] == y) {
      return i;
    } else if (
      (points[i][0] == x || points[i][1] == y) &&
      (smallest == undefined || smallest >= manhattan)
    ) {
      if (smallest === manhattan) {
        count++;
      } else {
        count = 1;
        index = i;
      }
      smallest = manhattan;
    }
  }

  return count >= 1 ? index : -1;
}