Course4all

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

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Graphs.

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

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional weighted edge between cities from_i and to_i, and given the integer distanceThreshold.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold. If there are multiple such cities, return the city with the greatest number.

Visual Representation

Cities 4, Edges: [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], Threshold 4 0 --3-- 1 --1-- 2 \ / 4---3 (1) City 0: Neighbors {1,2} (Dist 3, 4) - Count 2 City 3: Neighbors {1,2} (Dist 2, 1) - Count 2 ... compare all, find min count.
Hard

Examples

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
City 3 has 2 neighbors within distance 4, same as city 0, but 3 > 0.
Approach 1

Level III: Optimal (Floyd-Warshall Algorithm)

Intuition

This problem requires finding all-pairs shortest paths to count how many cities are within the threshold for each city. Floyd-Warshall is the standard algorithm for all-pairs shortest paths in a small number of vertices (N≤100N \\≤ 100).

Thought Process

  1. Initialize a dist matrix of size N×NN \times N with infinity, and dist[i][i] = 0.
  2. For each edge (u, v, w), set dist[u][v] = dist[v][u] = w.
  3. Run Floyd-Warshall: three nested loops k, i, j to update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  4. For each city i, count how many j have dist[i][j] <= distanceThreshold.
  5. Tracking the minimum count and the maximum index among cities with that count.

Pattern: All-Pairs Shortest Path

⏱ O(N^3) (three nested loops).💾 O(N^2) for the distance matrix.

Detailed Dry Run

N=4, Threshold=4
  • After Floyd-Warshall, dist[0][1]=3, dist[0][2]=4, dist[0][3]=5.
  • City 0 count (<= 4): 2 (cities 1 and 2).
  • City 3 count (<= 4): dist[3][1]=2, dist[3][2]=1, dist[3][0]=5. Count 2 (cities 1 and 2).
  • Since counts are equal, pick city 3 (larger index).
java
import java.util.*;

public class Main {
    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], 1000000); // Infinity
            dist[i][i] = 0;
        }
        for (int[] e : edges) {
            dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int minCount = n, resultLocal = -1;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (dist[i][j] <= distanceThreshold) count++;
            }
            if (count <= minCount) {
                minCount = count;
                resultLocal = i;
            }
        }
        return resultLocal;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionShortest Path to Get All Keys
Next Question →Invert Binary Tree