nearestcity.java

Nearest Neighbour City

A number of cities are arranged on a graph that has been divided up like an ordinary Cartesian plane. Each city is located at an integral (x, y) coordinate intersection. City names and locations are given in the form of three arrays: c, x, and y, which are aligned by the index to provide the city name (c[i]), and its coordinates, (x[i], y[i]). Determine the name of the nearest city that shares either an x or a y coordinate with the queried city. If no other cities share an x or y coordinate, return 'NONE'. If two cities have the same distance to the queried city, q[i], consider the one with an alphabetically shorter name (i.e. 'ab' < 'aba' < 'abb') as the closest choice. The distance is the Manhattan distance, the absolute difference in x plus the absolute difference in y.

The time complexity for my solution is O(NlogK) for processing input + O(QlogK) for returning the result for all the given queries,
where N is the number of cities, K is the max number of cities with same x or y coordinate and Q is the number of queries.

(I ran out of time before I could run for the given testcases)

class Result {
    static class CityCoordinate implements Comparable<CityCoordinate>{
        int coordinate;
        String cityname;

        public CityCoordinate(int c, String city) {
            this.coordinate = c;
            this.cityname = city;
        }

        @Override
        public int compareTo(CityCoordinate c) {
            return Integer.compare(this.coordinate, c.coordinate);
        }
    }

    public static List<String> closestStraightCity(List<String> c, List<Integer> x, List<Integer> y, List<String> queries) {
        Map<String, int[]> cities = new HashMap<>();
        Map<Integer, List<CityCoordinate>> xMap = new HashMap<>();
        Map<Integer, List<CityCoordinate>> yMap = new HashMap<>();

        int N = c.size();
        for(int i=0; i<N; i++) {
            List<CityCoordinate> xList = xMap.getOrDefault(x.get(i), new ArrayList<>());
            xList.add(new CityCoordinate(y.get(i), c.get(i)));
            xMap.put(x.get(i), xList);

            List<CityCoordinate> yList = yMap.getOrDefault(y.get(i), new ArrayList<>());
            yList.add(new CityCoordinate(x.get(i), c.get(i)));
            yMap.put(y.get(i), yList);

            cities.put(c.get(i), new int[] {x.get(i), y.get(i)});
        }

        // For each x coordinate, sort the corresponding list of cities on y coordinate
        for(int xCoodinate : xMap.keySet()) {
            Collections.sort(xMap.get(xCoodinate));
        }

        // For each y coordinate, sort the corresponding list of cities on x coordinate
        for(int yCoodinate : yMap.keySet()) {
            Collections.sort(yMap.get(yCoodinate));
        }


        List<String> result = new ArrayList<>();
        for(String q : queries) {
            int[] location = cities.get(q);

            List<CityCoordinate> xList = xMap.get(location[0]);
            List<CityCoordinate> yList = yMap.get(location[1]);

            CityCoordinate closestX = getClosestCityOnAnAxis(xList, location[1], q);
            CityCoordinate closestY = getClosestCityOnAnAxis(yList, location[0], q);

            result.add(getClosestCity(closestX, closestY, location));
        }

        return result;
    }

    private static String getClosestCity(CityCoordinate xCity, CityCoordinate yCity, int[] location) {
        int manhattanDistance1 = Math.abs(location[0] - xCity.coordinate);
        int manhattanDistance2 = Math.abs(location[1] - yCity.coordinate);

        if(manhattanDistance1 < manhattanDistance2) {
            return xCity.cityname;
        } else if(manhattanDistance1 == manhattanDistance2) {
            return xCity.cityname.compareTo(yCity.cityname) < 0 ? xCity.cityname : yCity.cityname;
        } else {
            return yCity.cityname;
        }
    }

    private static CityCoordinate getClosestCityOnAnAxis(List<CityCoordinate> list, int location, String city) {
        int index = Collections.binarySearch(list, new CityCoordinate(location, city));
        CityCoordinate leftCity = null, rightCity = null;
        int leftDist = Integer.MAX_VALUE, rightDist = Integer.MAX_VALUE;

        if(index > 0) {
            leftCity = list.get(index - 1);
            leftDist = Math.abs(leftCity.coordinate - location);
        }

        if(index < list.size() - 1) {
            rightCity = list.get(index + 1);
            rightDist = Math.abs(rightCity.coordinate - location);
        }

        if(leftDist < rightDist) {
            return leftCity;
        } else if(leftDist == rightDist) {
            return leftCity.cityname.compareTo(rightCity.cityname) < 0 ? leftCity : rightCity;
        } else {
            return rightCity;
        }
    }
}