Find the City With the Smallest Number of Neighbors

35 min · findTheCity()

A city wants the quietest hub: the place with the fewest nearby neighbors by road distance, not by the number of direct roads.

You receive n cities numbered from 0 through n - 1. Each [u, v, w] in edges is an undirected edge — a road that can be used both ways and has length w.

For each city, count how many other cities can be reached with a shortest-route distance no greater than distanceThreshold. Return the city with the smallest count. When several cities share that count, return the one with the greatest index.

Roads don't connect a city to itself, and each unordered pair appears at most once. The graph may be disconnected.

Constraints

2 <= n <= 100
0 <= edges.length <= n * (n - 1) / 2
Every edges[i] is [u, v, w] with 0 <= u, v < n, u != v, and 1 <= w <= 10_000.
No undirected city pair appears twice.
0 <= distanceThreshold <= 10_000

Hints

Direct roads aren't enough

A city may be within the threshold through several roads. You need shortest-path distances between every pair of cities, not just the edges you were given.

Think all-pairs

Build an n × n distance table: zero on the diagonal, road weights where edges exist, and infinity elsewhere. Then try every city as an allowed middle stop.

Let the tie rule shape the loop

Scan cities from smallest to largest and replace the answer when a count is less than or equal to the best count. Equality then naturally keeps the larger index.

Follow-up

If n were huge but the road map were sparse, would running a single-source algorithm from each city become more attractive than an n × n table?

Visible cases

Examples

Example 1

ready

Input: n = 4 edges = [ [ 0, 1, 3 ], [ 1, 2, 1 ], [ 1, 3, 4 ], [ 2, 3, 1 ] ] distanceThreshold = 4
Expected: 3
Why: city 3 reaches two neighbors; ties favor the greatest index

Example 2

ready

Input: n = 5 edges = [ [ 0, 1, 2 ], [ 0, 4, 8 ], [ 1, 2, 3 ], [ 1, 4, 2 ], [ 2, 3, 1 ], [ 3, 4, 1 ] ] distanceThreshold = 2
Expected: 0
Why: only city 1 is within distance 2 of city 0

Example 3

ready

Input: n = 2 edges = [ [ 0, 1, 3 ] ] distanceThreshold = 3
Expected: 1
Why: both cities reach one neighbor, so city 1 wins the tie

Interview signal

Asked at

AmazonGoogle

Dijkstra from every city — repeat single-source shortest paths

Dijkstra is a valid choice because every road weight is non-negative. Run it once from each city, count the distances at or below the threshold, and keep the smallest count. A min-heap makes each run efficient on a sparse road map, but the repeated setup and heap work add up when the graph is dense.

import heapq
 
 
def find_the_city(
    n: int,
    edges: list[list[int]],
    distance_threshold: int,
) -> int:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for city_a, city_b, distance in edges:
        graph[city_a].append((city_b, distance))
        graph[city_b].append((city_a, distance))
 
    def reachable_count(source: int) -> int:
        distances = [float("inf")] * n
        distances[source] = 0
        queue = [(0, source)]
        while queue:
            distance, city = heapq.heappop(queue)
            if distance != distances[city]:
                continue
            for neighbor, road in graph[city]:
                candidate = distance + road
                if candidate < distances[neighbor]:
                    distances[neighbor] = candidate
                    heapq.heappush(queue, (candidate, neighbor))
        return sum(
            city != source and distance <= distance_threshold
            for city, distance in enumerate(distances)
        )
 
    answer, fewest = -1, float("inf")
    for city in range(n):
        count = reachable_count(city)
        if count <= fewest:
            answer, fewest = city, count
    return answer

Time O(V(V + E) log V) for V heap-based Dijkstra runs. Space O(V + E) for the adjacency list, one distance array, and one heap.

Floyd-Warshall — solve every pair together

Floyd-Warshall is the right choice because the answer needs all-pairs shortest paths and n is at most 100. Its table starts with direct-road distances. For each possible middle city mid, update every pair:

distance[a][b] = min(distance[a][b], distance[a][mid] + distance[mid][b])

After mid has advanced through every city, the table contains true shortest distances.

def find_the_city(
    n: int,
    edges: list[list[int]],
    distance_threshold: int,
) -> int:
    distances = [[float("inf")] * n for _ in range(n)]
    for city in range(n):
        distances[city][city] = 0
    for city_a, city_b, distance in edges:
        distances[city_a][city_b] = distance
        distances[city_b][city_a] = distance
 
    for middle in range(n):
        for start in range(n):
            for end in range(n):
                through_middle = distances[start][middle] + distances[middle][end]
                if through_middle < distances[start][end]:
                    distances[start][end] = through_middle
 
    answer, fewest = -1, n
    for city in range(n):
        count = sum(
            other != city and distances[city][other] <= distance_threshold
            for other in range(n)
        )
        if count <= fewest:
            answer, fewest = city, count
    return answer

Using <= in the final comparison is intentional. Cities are scanned in increasing order, so an equal count replaces the earlier answer with the greater index.

Time O(V³) for the three table loops. Space O(V²) for all pairwise distances.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayn: int · edges: int[][] · distanceThreshold: int

Expected

Run: visible + custom · Submit: full suite