Nearest Neighboring City - Find the Closest City Along the Same Axis

Question

## Round 1 - Coding

## Problem

Given a list of cities, each with unique x and y coordinates, for each city find the nearest city that shares either the same x-coordinate or the same y-coordinate. If no such city exists, return an empty string.

```python
def find_nearest_city(
    num_cities: int,
    cities: list[str],
    x: list[int],
    y: list[int]
) -> list[str]:
    # For city i, find the name of the nearest city sharing x[i] or y[i]
    # Distance = Manhattan distance |x1-x2| + |y1-y2| (reduces to axis difference)
    # Return empty string if no same-axis neighbor
    ...
```

```
Example:
cities = ["Brighton", "Harrow", "Islington"]
x      = [2, 2, 5]
y      = [4, 6, 4]

Brighton  (2,4): shares x=2 with Harrow (2,6) -> dist 2; shares y=4 with Islington (5,4) -> dist 3 -> Harrow
Harrow    (2,6): shares x=2 with Brighton (2,4) -> dist 2 -> Brighton
Islington (5,4): shares y=4 with Brighton (2,4) -> dist 3; no x-share -> Brighton

find_nearest_city(...) -> ["Harrow", "Brighton", "Brighton"]
```

## Follow-ups

1. How do you efficiently group cities by shared x and y coordinates?
2. What is the time complexity of your approach?
3. How would you handle ties (two neighbors at the same distance on the same axis)?
4. How does the solution change if coordinates are floating point with precision issues?

Nearest Neighboring City - Find the Closest City Along the Same Axis

Question Details

Full Details

Topics

More from DoorDash