Course4all
Join us on telegram
Home/dsa/Graphs/Find the City With the Smallest Number of Neighbors at a Threshold Distance

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

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionShortest Path to Get All Keys
Next Question →Invert Binary Tree