Problem Description

You are given n cities numbered from 0 to n - 1. There are also edges, where each edge is represented as [from, to, weight] and indicates an undirected road between city from and city to with a distance of weight. Given an integer distanceThreshold, your task is to find the city with the smallest number of cities that are reachable from it via paths whose total distance is at most distanceThreshold. If there are multiple such cities, return the city with the greatest number.

• Each path can use multiple edges, but the total distance must not exceed distanceThreshold.
• Return the city with the smallest number of reachable neighbors within the threshold.
• If multiple cities have the same number, return the city with the greatest index.

Thought Process

The problem is essentially about determining, for each city, how many other cities it can reach using paths whose total distance does not exceed a given threshold. For each city, we must compute the shortest path to every other city, then count how many of these shortest paths are within the threshold.

A brute-force approach would be to check all possible paths from every city to every other city and see if the path cost is within the threshold. However, this is very inefficient, especially as the number of cities grows.

Instead, we recognize this as a shortest-paths problem. For all-pairs shortest paths, we can use the Floyd-Warshall algorithm, which efficiently computes the shortest distance between every pair of cities. Once we have these distances, we can simply count, for each city, how many other cities are reachable within the threshold.

Solution Approach

• Step 1: Initialize Distance Matrix
  • Create an n x n matrix where dist[i][j] represents the shortest known distance from city i to city j.
  • Set dist[i][j] to infinity for all i != j, and 0 for i == j.
  • For each edge, update dist[from][to] and dist[to][from] to the edge's weight, since the graph is undirected.
• Step 2: Floyd-Warshall Algorithm
  • Iterate over all possible intermediate cities k.
  • For each pair of cities i and j, check if going through k offers a shorter path: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  • This step computes the shortest paths between all pairs of cities.
• Step 3: Count Reachable Cities
  • For each city i, count the number of cities j such that i != j and dist[i][j] <= distanceThreshold.
• Step 4: Find the Desired City
  • Track the city with the smallest count of reachable cities. If there is a tie, pick the city with the greater index.

We use the Floyd-Warshall algorithm because it efficiently computes all-pairs shortest paths in O(n³) time, which is manageable for the constraints (typically n ≤ 100).

Example Walkthrough

Sample Input:
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4

• Step 1: Distance Matrix Initialization
  dist = [ [0, 3, ∞, ∞], [3, 0, 1, 4], [∞, 1, 0, 1], [∞, 4, 1, 0] ]
• Step 2: Floyd-Warshall Updates
  After running the algorithm, the shortest paths are:
  dist = [ [0, 3, 4, 5], [3, 0, 1, 2], [4, 1, 0, 1], [5, 2, 1, 0] ]
• Step 3: Counting Reachable Cities
  • City 0 can reach city 1 (3) and city 2 (4): 2 cities
  • City 1 can reach 0 (3), 2 (1), 3 (2): 3 cities
  • City 2 can reach 0 (4), 1 (1), 3 (1): 3 cities
  • City 3 can reach 1 (2), 2 (1): 2 cities
• Step 4: Choosing the City
  • Cities 0 and 3 both have 2 reachable cities, so we choose city 3 (the greater index).

Time and Space Complexity

• Brute-force Approach:
  • Time: Exponential, as we would need to enumerate all paths between every pair of cities.
  • Space: Potentially exponential for storing all paths.
• Optimized (Floyd-Warshall) Approach:
  • Time: O(n³), since for each of the n nodes, we update an n x n matrix.
  • Space: O(n²), for the distance matrix.
• This is feasible for n up to about 100.

Summary

The problem asks us to find the city with the smallest number of neighbors within a threshold distance, using the shortest paths. By recognizing this as an all-pairs shortest path problem, we can use the Floyd-Warshall algorithm to efficiently compute the necessary distances. Counting reachable cities for each node and breaking ties by city index gives us the correct and optimal solution.

Code Implementation

class Solution:
    def findTheCity(self, n, edges, distanceThreshold):
        INF = float('inf')
        dist = [[INF] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
        for u, v, w in edges:
            dist[u][v] = min(dist[u][v], w)
            dist[v][u] = min(dist[v][u], w)
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        min_count = n + 1
        result = -1
        for i in range(n):
            count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
            if count <= min_count:
                min_count = count
                result = i
        return result
      

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const int INF = 1e9;
        vector<vector<int>> dist(n, vector<int>(n, INF));
        for (int i = 0; i < n; ++i) dist[i][i] = 0;
        for (auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            dist[u][v] = min(dist[u][v], w);
            dist[v][u] = min(dist[v][u], w);
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        int minCount = n + 1, res = -1;
        for (int i = 0; i < n; ++i) {
            int count = 0;
            for (int j = 0; j < n; ++j)
                if (i != j && dist[i][j] <= distanceThreshold)
                    ++count;
            if (count <= minCount) {
                minCount = count;
                res = i;
            }
        }
        return res;
    }
};
      

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = 1000000000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dist[i][j] = (i == j) ? 0 : INF;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            dist[u][v] = Math.min(dist[u][v], w);
            dist[v][u] = Math.min(dist[v][u], w);
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        int minCount = n + 1, res = -1;
        for (int i = 0; i < n; ++i) {
            int count = 0;
            for (int j = 0; j < n; ++j)
                if (i != j && dist[i][j] <= distanceThreshold)
                    ++count;
            if (count <= minCount) {
                minCount = count;
                res = i;
            }
        }
        return res;
    }
}
      

var findTheCity = function(n, edges, distanceThreshold) {
    const INF = 1e9;
    const dist = Array.from({length: n}, () => Array(n).fill(INF));
    for (let i = 0; i < n; ++i) dist[i][i] = 0;
    for (const [u, v, w] of edges) {
        dist[u][v] = Math.min(dist[u][v], w);
        dist[v][u] = Math.min(dist[v][u], w);
    }
    for (let k = 0; k < n; ++k)
        for (let i = 0; i < n; ++i)
            for (let j = 0; j < n; ++j)
                if (dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    let minCount = n + 1, res = -1;
    for (let i = 0; i < n; ++i) {
        let count = 0;
        for (let j = 0; j < n; ++j)
            if (i !== j && dist[i][j] <= distanceThreshold)
                ++count;
        if (count <= minCount) {
            minCount = count;
            res = i;
        }
    }
    return res;
};