Find Nearest Point That Has the Same X or Y Coordinate

Find Nearest Point That Has the Same X or Y Coordinate - Problem

Array Easy

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).

Input & Output

Example 1 — Basic Case

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

› Output: 0

💡 Note: Point [1,3] shares x=1 with distance |1-1|+|3-2|=1. Point [3,2] shares y=2 with distance |3-1|+|2-2|=2. Point [2,2] shares y=2 with distance |2-1|+|2-2|=1. Points 0 and 2 both have minimum distance 1, but index 0 is smaller.

Example 2 — No Valid Points

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

› Output: -1

💡 Note: Point [2,3] doesn't share x=1 or y=1. Point [3,2] doesn't share x=1 or y=1. No valid points exist.

Example 3 — Exact Match

$ Input: x = 1, y = 1, points = [[1,1],[2,1],[1,2]]

› Output: 0

💡 Note: Point [1,1] is exactly at our location with distance 0. Even though other points are valid, distance 0 is minimum possible.

Constraints

1 ≤ points.length ≤ 10⁴
points[i].length == 2
-10⁴ ≤ x, y, ai, bi ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Current position (1,2) and array of points [[1,3],[3,2],[2,2]]

Filter

Only consider points sharing x=1 or y=2 coordinate

Calculate

Find minimum Manhattan distance among valid points

Key Takeaway

🎯 Key Insight: Only points sharing the same x or y coordinate are valid candidates

Asked in

a Amazon 15 M Microsoft 8

The key insight is to only consider points that share the same x or y coordinate as our current position. The most efficient approach uses a single linear scan to find the valid point with minimum Manhattan distance, with early termination optimization when distance 0 is found. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Early Termination Optimization	O(n)	O(1)	Stop early when we find a point at the same location
Linear Scan	O(n)	O(1)	Check every point to find the closest valid one

Early Termination Optimization — Algorithm Steps

Step 1: Iterate through points checking validity
Step 2: Calculate Manhattan distance for valid points
Step 3: If distance is 0, return immediately (can't get closer)

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Check points sequentially for validity

Distance 0

If we find exact match, return immediately

Otherwise

Continue tracking minimum distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int x, int y, int points[][2], int pointsSize) {
    int minDistance = INT_MAX;
    int bestIndex = -1;
    
    for (int i = 0; i < pointsSize; i++) {
        int px = points[i][0];
        int py = points[i][1];
        
        // Check if point is valid (shares x or y coordinate)
        if (px == x || py == y) {
            // Calculate Manhattan distance
            int distance = abs(px - x) + abs(py - y);
            
            // If distance is 0, we found the closest possible point
            if (distance == 0) {
                return i;
            }
            
            // Update minimum if this distance is smaller
            if (distance < minDistance) {
                minDistance = distance;
                bestIndex = i;
            }
        }
    }
    
    return bestIndex;
}

int main() {
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for 2D array
    int points[100][2];
    int pointsSize = 0;
    
    char* ptr = strchr(line, '[');
    ptr++; // Skip first [
    
    while (ptr && *ptr) {
        if (*ptr == '[') {
            ptr++;
            points[pointsSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            points[pointsSize][1] = atoi(ptr);
            pointsSize++;
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
        } else {
            ptr++;
        }
    }
    
    int result = solution(x, y, points, pointsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Best case O(1) if first point is at same location, worst case O(n)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

24.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Early Termination Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler