1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

BFS with PQ

T: O(m + n*mlogn + nlogn)
S: O(n^2)

Time is better, not sure why Floyd is faster?

class Solution {
    private record Step(int node, int weight){};
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        Map<Integer, List<Step>> graph = new HashMap<>();
        buildGraph(edges, graph); //O(m)

        Map<Integer, List<Integer>> resultMap = new HashMap<>();
        for (int i = 0; i < n; i++) { 
            resultMap.put(i, new ArrayList<>()); // maybe there are nodes with no path, so it will be 0 size, win!
            bfs(i, graph, distanceThreshold, resultMap); // m*logn
        } // O(n*mlogn)
        List<Integer> list = new ArrayList<>(resultMap.keySet());
        list.sort((a, b) -> { // O(nlogn)
            if (resultMap.get(a).size() != resultMap.get(b).size()) {
                return resultMap.get(a).size() - resultMap.get(b).size();
            } else {
                return b - a;
            }
        });
        return list.get(0);
    }
    private void bfs(int start, Map<Integer, List<Step>> graph, int distanceThreshold, Map<Integer, List<Integer>> resultMap) {
        Queue<Step> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        Set<Integer> visited = new HashSet<>();
        pq.offer(new Step(start, 0));

        while (!pq.isEmpty()) {
            Step cur = pq.poll();
            if (visited.contains(cur.node)) {
                continue;
            }
            visited.add(cur.node);
            if (cur.weight > distanceThreshold) {
                continue;
            }
            if (cur.node != start) {
                resultMap.get(start).add(cur.node);
            }
            if (!graph.containsKey(cur.node)) {
                continue;
            }
            for (Step next : graph.get(cur.node)) {
                pq.offer(new Step(next.node, cur.weight + next.weight));
            }
        }
    }
    private void buildGraph(int[][] edges, Map<Integer, List<Step>> map) {
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new Step(edge[1], edge[2]));
            map.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new Step(edge[0], edge[2]));
        }
    }
}

/***

)  space.
explain: fully connected graph.
resultMap:
0 -> [1, 2, ..., n-1]  // n-1 elements
1 -> [0, 2, ..., n-1]  // n-1 elements
...
n-1 -> [0, 1, ..., n-2]  // n-1 elements
so edges are, n node -> link to n-1 node -> so it's O(n^2)





the "smallest number" of cities that are reachable 
through some path and whose distance is at most distanceThreshold


for (n)
 -> bfs, but. each <= distanceThreshold


 map<key, list> 

0. -   3
   \ /  |
    1 \ 
     4- 2

 */

Floyd

T: O(n^3)
S: O(n^2)

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) { // set init value for all dist (large value)
            Arrays.fill(dist[i], 10001);
            dist[i][i] = 0;
        }
        for (int[] edge : edges) { // set edges
            dist[edge[0]][edge[1]] = edge[2];
            dist[edge[1]][edge[0]] = edge[2];
        }
        for (int k = 0; k < n; k++) { // floyd algo to calculate all dist between i and j
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        int result = -1;
        int minCityCount = n;
        for (int i = 0; i < n; i++) {
            int cityCount = 0;
            for (int j = 0 ; j < n; j++) {
                if (dist[i][j] <= distanceThreshold) {
                    cityCount++;
                }
            }
            if (cityCount <= minCityCount) { // keep smallest cityCount which is < distanceThreshold
                minCityCount = cityCount;
                result = i;
            }
        }
        return result;
    }
}

/***
T: O(n^3)
S: O(n^2)

 */