Find the Nearest City

Overview

The problem asks us to find the nearest neighbor for a set of query cities, with the constraint that the neighbor must share either the same x-coordinate or the same y-coordinate. Since the distance calculation only involves one changing dimension (either $x$ or $y$ stays constant), the Manhattan distance simplifies to the absolute difference of the non-matching coordinate.

To solve this efficiently, we need a way to quickly group cities by their $x$ and $y$ coordinates. Searching through all cities for every query is too slow given that both the number of cities and queries can reach $10^5$. Instead, we should use hash maps to store lists of cities for each unique coordinate and sort these lists to allow for binary search or efficient neighbor lookups.

Brute Force

The brute force approach involves iterating through the entire list of cities for every query. For a given query city, we check every other city to see if it shares an x or y coordinate. If it does, we calculate the distance and maintain the minimum distance and the lexicographically smallest city name.

Implementation

def find_nearest_cities(cities: list[str], xCoordinates: list[int], yCoordinates: list[int], queries: list[str]) -> list[str]:
    city_map = {name: (x, y) for name, x, y in zip(cities, xCoordinates, yCoordinates)}
    ans = []
    
    for q in queries:
        if q not in city_map:
            ans.append("")
            continue
            
        q_x, q_y = city_map[q]
        best_dist = float('inf')
        best_city = ""
        
        for i in range(len(cities)):
            c_name = cities[i]
            if c_name == q:
                continue
            
            c_x, c_y = xCoordinates[i], yCoordinates[i]
            
            if c_x == q_x or c_y == q_y:
                dist = abs(c_x - q_x) + abs(c_y - q_y)
                if dist < best_dist:
                    best_dist = dist
                    best_city = c_name
                elif dist == best_dist:
                    if best_city == "" or c_name < best_city:
                        best_city = c_name
        
        ans.append(best_city)
    return ans

Time complexity: O(Q * N) — Where $Q$ is the number of queries and $N$ is the number of cities. Space complexity: O(N) — To store the mapping from city name to coordinates.

Optimal / Best Approach

The optimal approach pre-processes the cities into two maps: one grouping cities by $x$ coordinates and another by $y$ coordinates.

1. Preprocessing: Build a dictionary x_map where keys are x-coordinates and values are lists of (y_coordinate, city_name). Do the same for y_map.
2. Sorting: Sort each list in the maps. Since we need to find the nearest neighbor, sorting by coordinate allows us to use binary search.
3. Querying: For each query city:
   • Locate its position in the sorted list of cities sharing its $x$ coordinate using bisect_left.
   • The potential nearest neighbors on the $x$-axis are the cities immediately to the left and right in the sorted list.
   • Repeat the process for the $y$ coordinate.
   • Compare the (up to) four candidates to find the minimum distance and handle tie-breaking lexicographically.

Implementation

from bisect import bisect_left

def find_nearest_cities(cities: list[str], xCoordinates: list[int], yCoordinates: list[int], queries: list[str]) -> list[str]:
    x_map = {} # x -> sorted list of (y, name)
    y_map = {} # y -> sorted list of (x, name)
    city_to_coords = {} # name -> (x, y)
    
    for i in range(len(cities)):
        name, x, y = cities[i], xCoordinates[i], yCoordinates[i]
        city_to_coords[name] = (x, y)
        if x not in x_map: x_map[x] = []
        if y not in y_map: y_map[y] = []
        x_map[x].append((y, name))
        y_map[y].append((x, name))
        
    for x in x_map: x_map[x].sort()
    for y in y_map: y_map[y].sort()
    
    results = []
    for q in queries:
        if q not in city_to_coords:
            results.append("")
            continue
            
        x, y = city_to_coords[q]
        candidates = []
        
        # Check neighbors sharing same x
        x_list = x_map[x]
        idx = bisect_left(x_list, (y, q))
        for i in [idx - 1, idx + 1]:
            if 0 <= i < len(x_list):
                dist = abs(x_list[i][0] - y)
                candidates.append((dist, x_list[i][1]))
                
        # Check neighbors sharing same y
        y_list = y_map[y]
        idx = bisect_left(y_list, (x, q))
        for i in [idx - 1, idx + 1]:
            if 0 <= i < len(y_list):
                dist = abs(y_list[i][0] - x)
                candidates.append((dist, y_list[i][1]))
        
        if not candidates:
            results.append("")
        else:
            # Sort by distance (asc), then by name (lexicographical)
            candidates.sort(key=lambda x: (x[0], x[1]))
            results.append(candidates[0][1])
            
    return results

Time complexity: O(N log N + Q log N) — Preprocessing and sorting take $O(N \log N)$. Each of the $Q$ queries takes $O(\log N)$ due to binary search. Space complexity: O(N) — Storing the coordinate maps and the city lookup table.

Why this works

By sorting the cities sharing a coordinate, we narrow down the search space from $N$ potential cities to just 2 (the immediate predecessor and successor). Since any city further away in a sorted list will mathematically have a larger Manhattan distance, we only ever need to check these immediate neighbors. The $O(N \log N)$ initial investment pays off significantly when handling a large number of queries.