Find the City With the Smallest Number of Neighbors at a Threshold Distance Medium 0 attempts
LeetCode ↗

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

Medium GraphBFSDFS LeetCode

There are n cities numbered from 0 to n-1. Given edges where edges[i] = [from, to, weight] represents a bidirectional weighted edge, and an integer distanceThreshold, return the city with the smallest number of cities reachable within distanceThreshold. If multiple cities qualify, return the one with the greatest index. A city is reachable if the shortest path distance is at most distanceThreshold.

Example:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Sample Input
—
Sample Output
—
Constraints
  • 2 <= n <= 100
  • 1 <= edges.length <= n*(n-1)/2
  • 0 <= distanceThreshold <= 10^4
Test Cases
Case 1
Args: [4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4] Expected: 3
Topics
GraphBFSDFS

Approach: Floyd-Warshall

Compute all-pairs shortest paths using Floyd-Warshall. For each city, count how many other cities are reachable within the threshold. Return the city with the smallest count, breaking ties by largest index.

function findTheCityWithTheSmallestNumberOfNeighborsAtAThresholdDistance(n, edges, distanceThreshold) {
  const dist = Array.from({length: n}, () => Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const [u, v, w] of edges) { dist[u][v] = w; 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++)
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
  let result = -1, minCount = Infinity;
  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; result = i; }
  }
  return result;
}

Time Complexity: O(n³)

Space Complexity: O(n²)

Saved in this browser only. Private to you.

JavaScript