Find the City With the Fewest Reachable Neighbours

Problem and examples

Given n cities numbered from 0 to n - 1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional road between cities from_i and to_i with travel distance weight_i, you are also given a distance threshold distanceThreshold.

Your task is to find the city with the smallest number of other cities that can be reached from it through any path such that the total distance is less than or equal to distanceThreshold.

If there are multiple cities with the same minimal number of reachable neighbours, return the city with the greatest number.

n	Edges	Threshold	Output	Description
4	[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]	4	3	City 3 can reach only city 2 within threshold 4
5	[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]	2	0	City 0 can reach only city 1 within threshold 2
2	[[0,1,10]]	5	1	No city can reach the other, return the city with the greatest index

How it works

Understanding the Problem

We are given n cities, numbered from 0 to n - 1, and a list of edges that represent bidirectional roads between cities. Each edge contains a source city, a destination city, and the distance between them. We are also given a distanceThreshold, which defines the maximum distance we can travel from any city.

Our goal is to find the city with the fewest number of reachable cities within this threshold. If there are multiple cities with the same minimum count, we return the city with the largest index.

Step-by-Step Solution with Example

Step 1: Understand the Input

Suppose we have n = 4 cities, the following edges:

[
  [0, 1, 3],
  [1, 2, 1],
  [2, 3, 4],
  [0, 3, 7]
]

And a distanceThreshold = 4.

Step 2: Represent the Graph

We create an adjacency matrix to represent the shortest distance between all pairs of cities. Initially, set the distance between each pair as Infinity, and set dist[i][i] = 0. Then fill in the given edges.

Step 3: Use Floyd-Warshall to Compute All-Pairs Shortest Paths

Floyd-Warshall is ideal when n is small (like ≤ 100). It updates the shortest distance between every pair of cities using a dynamic programming approach. For each intermediate city k, update:


if (dist[i][j] > dist[i][k] + dist[k][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
}

Step 4: Count Reachable Cities

For each city, count how many other cities are reachable such that dist[i][j] ≤ distanceThreshold. Do not count the city itself.

Step 5: Track the Best Candidate

As we compute the reachable count for each city, track the city with the fewest reachable cities. If there's a tie, choose the city with the higher index.

Step 6: Final Output

From our example, city 3 can reach only one city within distance 4, so it will be the answer.

Edge Cases

No reachable neighbors: A city completely disconnected from others within the threshold will have a count of 0.
Multiple cities with same count: We must return the one with the highest index.
Disconnected components: Floyd-Warshall handles this by keeping unreachable distances as Infinity.
Zero threshold: Only self-reachability is allowed, so all cities will have 0 reachable neighbors.

Finally

This problem is a great use case for the Floyd-Warshall algorithm, which efficiently handles all-pairs shortest paths for small graphs. By applying it, we can easily evaluate reachability for every city and determine the one that meets the problem's criteria. Always keep in mind the edge conditions, such as tie-breaking and unreachable nodes, to ensure a complete and accurate solution.

Initialize a 2D matrix dist with infinity, except dist[i][i] = 0.
Fill in direct distances from the edges input.
Run the Floyd-Warshall algorithm:
1. For each intermediate node k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
For each city, count the number of other cities it can reach with distance ≤ threshold.
Return the city with the fewest reachable cities (use max index in case of tie).

Implementation and efficiency

C implementation

#include <stdio.h>
#define INF 1000000

void floydWarshall(int n, int dist[n][n]) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

int findTheCity(int n, int edges[][3], int edgesSize, int distanceThreshold) {
    int dist[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 i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        dist[u][v] = w;
        dist[v][u] = w;
    }

    floydWarshall(n, dist);

    int result = -1, minReachable = n;
    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 <= minReachable) {
            minReachable = count;
            result = i;
        }
    }
    return result;
}

int main() {
    int edges1[][3] = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
    int result1 = findTheCity(4, edges1, 4, 4);
    printf("%d\n", result1); // Output: 3

    int edges2[][3] = {{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}};
    int result2 = findTheCity(5, edges2, 6, 2);
    printf("%d\n", result2); // Output: 0

    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

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) {
        dist[e[0]][e[1]] = e[2];
        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] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int result = -1, minReachable = n;
    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 <= minReachable) {
            minReachable = count;
            result = i;
        }
    }
    return result;
}

int main() {
    cout << findTheCity(4, {{0,1,3},{1,2,1},{1,3,4},{2,3,1}}, 4) << endl; // 3
    cout << findTheCity(5, {{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}}, 2) << endl; // 0
    return 0;
}

Python implementation

def find_the_city(n, edges, distance_threshold):
    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] = w
        dist[v][u] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    result = -1
    min_reachable = n
    for i in range(n):
        count = sum(1 for j in range(n) if i != j and dist[i][j] <= distance_threshold)
        if count <= min_reachable:
            min_reachable = count
            result = i

    return result

print(find_the_city(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4))  # 3
print(find_the_city(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2))  # 0

Java implementation

public class FindCity {
    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = 1000000;
        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[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
            dist[edge[1]][edge[0]] = edge[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 result = -1, minReachable = n;
        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 <= minReachable) {
                minReachable = count;
                result = i;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findTheCity(4, new int[][]{{0,1,3},{1,2,1},{1,3,4},{2,3,1}}, 4)); // 3
        System.out.println(findTheCity(5, new int[][]{{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}}, 2)); // 0
    }
}

JavaScript implementation

function findTheCity(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] = 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++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  let answer = -1;
  let minReachable = n;

  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 <= minReachable) {
      minReachable = count;
      answer = i;
    }
  }

  return answer;
}

console.log(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)); // 3
console.log(findTheCity(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2)); // 0

Go implementation

package main

import (
	"fmt"
	"math"
)

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
	const INF = math.MaxInt32 / 2
	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			if i == j {
				dist[i][j] = 0
			} else {
				dist[i][j] = INF
			}
		}
	}
	for _, edge := range edges {
		dist[edge[0]][edge[1]] = edge[2]
		dist[edge[1]][edge[0]] = edge[2]
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] = dist[i][k] + dist[k][j]
				}
			}
		}
	}

	result, minReachable := -1, n
	for i := 0; i < n; i++ {
		count := 0
		for j := 0; j < n; j++ {
			if i != j && dist[i][j] <= distanceThreshold {
				count++
			}
		}
		if count <= minReachable {
			minReachable = count
			result = i
		}
	}
	return result
}

func main() {
	fmt.Println(findTheCity(4, [][]int{{0,1,3},{1,2,1},{1,3,4},{2,3,1}}, 4)) // 3
	fmt.Println(findTheCity(5, [][]int{{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}}, 2)) // 0
}

Rust implementation

fn find_the_city(n: usize, edges: Vec<(usize, usize, i32)>, threshold: i32) -> i32 {
    let inf = 1_000_000;
    let mut dist = vec![vec![inf; n]; n];
    for i in 0..n {
        dist[i][i] = 0;
    }
    for (u, v, w) in edges {
        dist[u][v] = w;
        dist[v][u] = w;
    }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                let through_k = dist[i][k] + dist[k][j];
                if through_k < dist[i][j] {
                    dist[i][j] = through_k;
                }
            }
        }
    }
    let mut result = -1;
    let mut min_reach = n;
    for i in 0..n {
        let reachable = dist[i].iter().enumerate()
            .filter(|&(j, &d)| i != j && d <= threshold)
            .count();
        if reachable <= min_reach {
            min_reach = reachable;
            result = i as i32;
        }
    }
    result
}

fn main() {
    let res1 = find_the_city(4, vec![(0,1,3),(1,2,1),(1,3,4),(2,3,1)], 4);
    println!("{}", res1); // 3
    let res2 = find_the_city(5, vec![(0,1,2),(0,4,8),(1,2,3),(1,4,2),(2,3,1),(3,4,1)], 2);
    println!("{}", res2); // 0
}

Kotlin implementation

fun findTheCity(n: Int, edges: Array<IntArray>, distanceThreshold: Int): Int {
    val INF = 1_000_000
    val dist = Array(n) { IntArray(n) { INF } }
    for (i in 0 until n) dist[i][i] = 0

    for ((u, v, w) in edges) {
        dist[u][v] = w
        dist[v][u] = w
    }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    var result = -1
    var minReachable = n
    for (i in 0 until n) {
        val count = (0 until n).count { j -> i != j && dist[i][j] <= distanceThreshold }
        if (count <= minReachable) {
            minReachable = count
            result = i
        }
    }
    return result
}

fun main() {
    println(findTheCity(4, arrayOf(intArrayOf(0,1,3), intArrayOf(1,2,1), intArrayOf(1,3,4), intArrayOf(2,3,1)), 4)) // 3
    println(findTheCity(5, arrayOf(intArrayOf(0,1,2), intArrayOf(0,4,8), intArrayOf(1,2,3), intArrayOf(1,4,2), intArrayOf(2,3,1), intArrayOf(3,4,1)), 2)) // 0
}

Swift implementation

import Foundation

func findTheCity(_ n: Int, _ edges: [[Int]], _ distanceThreshold: Int) -> Int {
    let INF = 1_000_000
    var dist = Array(repeating: Array(repeating: INF, count: n), count: n)

    for i in 0..<n {
        dist[i][i] = 0
    }

    for edge in edges {
        let u = edge[0], v = edge[1], w = edge[2]
        dist[u][v] = w
        dist[v][u] = w
    }

    for k in 0..<n {
        for i in 0..<n {
            for j in 0..<n {
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    var result = -1
    var minReachable = n
    for i in 0..<n {
        let count = dist[i].enumerated().filter { i != $0.offset && $0.element <= distanceThreshold }.count
        if count <= minReachable {
            minReachable = count
            result = i
        }
    }
    return result
}

print(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)) // 3
print(findTheCity(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2)) // 0

TypeScript implementation

function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
  const INF = 1e9;
  const dist: number[][] = 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] = 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++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  let answer = -1;
  let minReachable = n;

  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 <= minReachable) {
      minReachable = count;
      answer = i;
    }
  }

  return answer;
}

console.log(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)); // 3
console.log(findTheCity(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2)); // 0