Skip to main content
Talentd

Find Nearest Point That Has the Same X or Y Coordinate - Solution & Explanation

EasyArray14 min readAsked at: Amazon, DoorDash, Google
Practice this problem

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

Approach Overview

Problem Overview: You are given your current location (x, y) and a list of points. A point is considered valid if it shares the same x coordinate or the same y coordinate. Among all valid points, return the index of the point with the smallest Manhattan distance from your location. If multiple points have the same distance, return the smallest index.

Approach 1: Iterative Approach Using Manhattan Distance (O(n) time, O(1) space)

Scan the array once and evaluate each point. A point is valid if px == x or py == y. For valid points, compute the Manhattan distance using |px - x| + |py - y|. Track the smallest distance seen so far along with its index. Because the scan proceeds from left to right, the first occurrence naturally preserves the smallest index when distances tie. This approach uses a simple loop and constant extra memory, making it optimal for problems involving array traversal.

Approach 2: Filter Valid Points and Find Minimum (O(n) time, O(n) space)

First filter the list to keep only points that share the same x or y coordinate. For each valid point, compute the Manhattan distance and store a tuple of (distance, index). After filtering, select the tuple with the smallest distance (and smallest index in case of ties). Many languages allow concise implementations using functional utilities such as filter, list comprehensions, or streams. This version separates validation from distance computation, which can improve readability when working with coordinate-based array problems or simple geometry logic.

Recommended for interviews: The single-pass iterative solution is what interviewers expect. It demonstrates you understand Manhattan distance and can solve the problem in one linear scan with constant space. The filtering approach is also linear but introduces extra memory and abstraction layers. Showing the direct scan first proves you can reason about constraints and implement an optimal O(n) solution quickly.

Approach 1: Iterative Approach Using Manhattan Distance

This approach involves iterating through each point in the array to check if it is valid, i.e., it shares either the x or y coordinate with the given point (x, y). If it is valid, we calculate the Manhattan distance from (x, y) to that point and update the minimum distance and corresponding index. Finally, we return the index of the point with the smallest distance.

In this C solution, we iterate over the array of points using a for loop and check if each point is valid (shares the x or y coordinate). For each valid point, we compute its Manhattan distance, and keep track of the smallest distance and its index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), since we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Use of Filter for Valid Points and Finding Minimum

This approach first filters out all invalid points, leaving only those that share the x or y coordinate with your position. After filtering, it computes the Manhattan distances for these valid points, finds the smallest distance, and returns the corresponding index.

This approach filters invalid points first by directly embedding the condition into the main loop. Valid points are then evaluated for their Manhattan distance, similar to the previous approach.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), n is the number of points.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach Using Manhattan Distance

Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), since we are using a constant amount of extra space.

Use of Filter for Valid Points and Finding Minimum

Time Complexity: O(n), n is the number of points.
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Manhattan Distance ScanO(n)O(1)Best general solution. Single pass through the array with minimal memory.
Filter Valid Points Then Compute MinimumO(n)O(n)Useful for cleaner functional-style code or when separating validation and computation logic.

Video Solution

1779. Find Nearest Point That Has the Same X or Y Coordinate (Leetcode Easy) • Programming Live with Larry • 2,391 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Find Nearest Point That Has the Same X or Y Coordinate easy or hard?
Find Nearest Point That Has the Same X or Y Coordinate is classified as an Easy problem on LeetCode. The task mainly tests understanding of Manhattan distance and basic array traversal. The optimal solution requires a straightforward O(n) scan with constant extra space.
Find Nearest Point That Has the Same X or Y Coordinate Python/Java solution
In Python or Java, iterate through the list of points and check if px == x or py == y. For valid points compute |px - x| + |py - y| and update the minimum distance if the value is smaller. Maintain the index of the best candidate during traversal to return the correct result.
How to solve Find Nearest Point That Has the Same X or Y Coordinate in O(n)?
Iterate through the array of points and check if the point shares the same x or y coordinate. If it does, compute the Manhattan distance using |px - x| + |py - y|. Keep track of the smallest distance and update the answer when a smaller distance is found. This single linear scan ensures O(n) time complexity.
What is the best approach for Find Nearest Point That Has the Same X or Y Coordinate?
The best approach is a single-pass iteration through the points while computing Manhattan distance for valid points. A point is valid if it shares the same x or y coordinate with the target location. Track the minimum distance and index during the scan. This runs in O(n) time and O(1) space.
Is Find Nearest Point That Has the Same X or Y Coordinate asked at Google/Amazon/Meta?
This problem represents a common array scanning and coordinate filtering pattern frequently used in coding interviews. Variants of Manhattan distance and coordinate matching appear in interviews at large tech companies such as Google, Amazon, and Meta as part of easy or warm‑up questions.
What data structure is used in Find Nearest Point That Has the Same X or Y Coordinate?
The primary data structure is an array of coordinate pairs. The algorithm performs a simple linear traversal of the array while computing Manhattan distance and tracking the minimum value. No additional data structures such as hash maps or heaps are required for the optimal solution.
What is the time complexity of Find Nearest Point That Has the Same X or Y Coordinate?
The optimal solution runs in O(n) time because each point is checked exactly once. The algorithm simply validates coordinates and calculates Manhattan distance. Space complexity is O(1) since only a few variables are used to track the best distance and index.

Ready to solve this problem?

Practice Find Nearest Point That Has the Same X or Y Coordinate with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Closest Points to Origin