01

Problem Statement

You are given a list of cities, each with a unique name and integer coordinates (x, y). For a query city, you need to find the nearest other city that shares either the same x-coordinate or the same y-coordinate.

  • Distance is measured by Manhattan distance: dist = |x1 - x2| + |y1 - y2|.
  • A candidate city must satisfy x1 == x2 or y1 == y2 with the query city.
  • If multiple cities are at the same minimum distance, return the lexicographically smallest name.
  • If the query city does not exist, or there is no valid candidate, return the empty string "".
02

Key Observations

  • Candidate cities only come from groups that share the same x or the same y; you never need to scan all cities.
  • When x is shared, distance simplifies to |y1 - y2|; when y is shared, it simplifies to |x1 - x2|.
  • After sorting each x-group by y and each y-group by x, the nearest candidate must be one of the immediate neighbors in that sorted order.
  • Use a unified tie-break rule on the pair (distance, name) so the comparison logic stays consistent.
03

Approach

High-level

Use preprocessing + binary search: build two hash maps x -> all cities in that column (sorted by y) and y -> all cities in that row (sorted by x). For each query, locate the query city in those sorted lists by binary search and only compare against its neighbors.

Steps

  1. Build a direct lookup name -> (x, y) for all cities.
  2. Build xGroups: Map<x, cities sorted by y>, where each key is an x-coordinate and the value is a list of cities sorted by y.
  3. Build yGroups: Map<y, cities sorted by x>, where each key is a y-coordinate and the value is a list of cities sorted by x.
  4. For a query city:
    • Binary search in its x-group by y and check the left/right neighbors as “same-x” candidates.
    • Binary search in its y-group by x and check the left/right neighbors as “same-y” candidates.
    • Compare all candidates using (distance, name) and pick the global minimum; if there is no candidate, return "".
04

Implementation

Java
import java.util.*;

class CityMap {

    private static class City {
        String name;
        int x;
        int y;
        City(String name, int x, int y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }
    }

    private final Map<String, City> byName = new HashMap<>();
    private final Map<Integer, List<City>> byX = new HashMap<>();
    private final Map<Integer, List<City>> byY = new HashMap<>();

    public CityMap(String[] names, int[] xs, int[] ys) {
        int n = names.length;

        for (int i = 0; i < n; i++) {
            City c = new City(names[i], xs[i], ys[i]);
            byName.put(c.name, c);
            byX.computeIfAbsent(c.x, k -> new ArrayList<>()).add(c);
            byY.computeIfAbsent(c.y, k -> new ArrayList<>()).add(c);
        }

        // sort groups for binary search

        for (List<City> list : byX.values()) {
            list.sort(Comparator.comparingInt(a -> a.y));
        }

        for (List<City> list : byY.values()) {
            list.sort(Comparator.comparingInt(a -> a.x));
        }
    }

    public String getNearestCity(String query) {
        City origin = byName.get(query);

        if (origin == null) {
            return "";
        }

        int bestDist = Integer.MAX_VALUE;
        String bestName = "";

        // candidates sharing same x
        List<City> sameX = byX.get(origin.x);

        if (sameX != null && sameX.size() > 1) {
            int idx = lowerBoundY(sameX, origin.y);
            bestName = updateFromGroup(origin, sameX, idx, bestDist, bestName);
            bestDist = distance(origin, bestName);
        }

        // candidates sharing same y
        List<City> sameY = byY.get(origin.y);

        if (sameY != null && sameY.size() > 1) {
            int idx = lowerBoundX(sameY, origin.x);
            bestName = updateFromGroup(origin, sameY, idx, bestDist, bestName);
        }

        return bestName;
    }

    private int distance(City a, City b) {

        if (b == null) {
            return Integer.MAX_VALUE;
        }

        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    private int distance(City a, String bName) {
        City b = byName.get(bName);

        if (b == null) {
            return Integer.MAX_VALUE;
        }

        return distance(a, b);
    }

    private String updateFromGroup(City origin, List<City> group, int idx, int currentBestDist, String currentBestName) {
        String bestName = currentBestName;
        int bestDist = currentBestDist;

        for (int offset = -1; offset <= 0; offset++) {
            int i = idx + offset;

            if (i < 0 || i >= group.size()) {
                continue;
            }

            City cand = group.get(i);

            if (cand.name.equals(origin.name)) {
                continue;
            }

            int d = distance(origin, cand);

            if (d < bestDist
            || (d == bestDist && (bestName.equals("") || cand.name.compareTo(bestName) < 0))) {
                bestDist = d;
                bestName = cand.name;
            }
        }

        return bestName;
    }

    private int lowerBoundY(List<City> list, int y) {
        int lo = 0, hi = list.size();

        while (lo < hi) {
            int mid = (lo + hi) >>> 1;

            if (list.get(mid).y < y) {
                lo = mid + 1;
            }
            else {
                hi = mid;
            }
        }

        return lo;
    }

    private int lowerBoundX(List<City> list, int x) {
        int lo = 0, hi = list.size();

        while (lo < hi) {
            int mid = (lo + hi) >>> 1;

            if (list.get(mid).x < x) {
                lo = mid + 1;
            }
            else {
                hi = mid;
            }
        }

        return lo;
    }
}
05

Test Cases

Basic case: nearest city exists

Input
names = ["a", "b", "c"], xs = [0, 0, 2], ys = [0, 2, 0], query = "a"
Expected
"b"
Explanation
a(0,0) shares x with b(0,2) (distance 2) and shares y with c(2,0) (also distance 2). Distances tie, but "b" < "c" lexicographically, so we return "b".
06

Complexity Analysis

  • Preprocessing: O(n log n) for grouping and sorting by x / y.
  • Query: O(log n) for two binary searches plus constant-time neighbor checks.
  • Space: O(n) to store all cities and index structures.
07

Follow-ups / Variations

  • How would you support dynamic insertion of cities while keeping the groups sorted? Would you use balanced trees, skip lists, or something else?
  • Is there any way to make queries O(1) in theory? Under what assumptions or approximations could that be possible?
  • If the tie-break changes to use an integer cityId instead of name, how would you adapt the comparison logic?
  • If distance changes to Euclidean distance, does the “neighbor in sorted list” idea still work, or do you need a more advanced spatial index (e.g. a kd-tree)?