Nearest Shared City
MediumMaps · DoorDash
You are given n cities. City i is named names[i] and sits at integer point (xs[i], ys[i]). No two cities share the same point.
For each name in queries, find the nearest *other* city that lies on the same vertical line (same x) or the same horizontal line (same y) as the queried city. Distance is Manhattan distance, which for two cities on a shared line is just the difference along the other coordinate.
- If several cities are equally near, choose the lexicographically smallest name.
- If no other city shares the queried city's x or y, the answer for that query is
"NONE".
Return a list with one answer per query, in the same order as queries.
Example 1
- Input:
- names = ["fremont", "oakland", "berkeley", "sanjose", "palo"], xs = [3, 3, 8, 3, 8], ys = [1, 6, 1, 9, 6], queries = ["fremont", "palo", "sanjose"]
- Output:
- ["berkeley", "berkeley", "oakland"]
- Explanation
fremont(3, 1) shares x withoakland(5 away) andsanjose(8 away), and shares y withberkeley(5 away); the tie at 5 goes toberkeley.palo(8, 6) is 5 from bothberkeleyandoakland, andberkeleywins the tie.sanjose(3, 9) shares only x, andoaklandis 3 away.
Example 2
- Input:
- names = ["a", "b", "c"], xs = [1, 2, 3], ys = [1, 2, 3], queries = ["b"]
- Output:
- ["NONE"]
- Explanation
bis close to both other cities, but neither shares its x or its y, so the answer is"NONE".
Example 3
- Input:
- names = ["m", "k", "z"], xs = [5, 5, 5], ys = [10, 4, 16], queries = ["m", "k"]
- Output:
- ["k", "m"]
- Explanation
mat y = 10 is 6 away from bothkandz, and"k"is the smaller name. Fork,mis 6 away andzis 12 away.
Constraints
1 <= n <= 10^5, andnames,xs,ysall have lengthn1 <= xs[i], ys[i] <= 10^9, and all points are distinct- City names are unique, non-empty lowercase strings
1 <= queries.length <= 10^5, and every query is one ofnames