EasyNo. 1779
Find Nearest Point That Has the Same X or Y Coordinate — LeetCode 1779 Python Solution
- Topics
- Array
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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).
Example
- 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.
Python solution
class Solution:
def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
ans, mi = -1, inf
for i, (a, b) in enumerate(points):
if a == x or b == y:
d = abs(a - x) + abs(b - y)
if mi > d:
ans, mi = i, d
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(1) to O(n)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
Frequently asked questions
- How hard is LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate?
LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate is rated Easy on LeetCode.
- What topics does LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate cover?
LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate is tagged Array on LeetCode.