# 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?

```java
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)
```

```java
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)

 */
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/graph-ii/floyd-algorithm/1334.-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.