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

Problem

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, 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.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Examples

Example 1:

graph LR;
	0 ---|3| 1
	1 ---|1| 2
	1 ---|4| 3
	2 ---|1| 3
  

Input:
n = 4, edges =[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output:
 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

graph LR;
	0 ---|2| 1
	0 ---|8| 4
	1 ---|3| 2
	1 ---|2| 4
	2 ---|1| 3
	3 ---|1| 4
  

Input:
n = 5, edges =[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output:
 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Solution

Why DFS will not work

Consider the graph with n = 6, edges =[[0,1,10],[0,2,1],[2,3,1],[1,3,1],[1,4,1],[4,5,10]], and let distanceThreshold = 20.

graph LR
	0 ---|10| 1
	0 ---|1| 2
	2 ---|1| 3
	1 ---|1| 3
	1 ---|1| 4
	4 ---|10| 5
  

Now, lets start DFS from node 0, and lets say we follow the path 0 -> 1 -> 4, then the visited set will be [0, 1, 4], but we will encounter error as distance to 5 is 21, which is more than distanceThreshold = 20. (See path below)

graph LR
	0 ---|10| 1
	0 ---|1| 2
	2 ---|1| 3
	1 ---|1| 3
	1 ---|1| 4
	4 ---|10| 5
	
linkStyle 0 stroke:gold, stroke-width:4px;
linkStyle 4 stroke:gold, stroke-width:4px;
linkStyle 5 stroke:gold, stroke-width:4px;
  

---
title: visited set
---
graph TD;
	A(0)
	B(1)
	C(2)
  

But actually, we can reach 5 if we follow the path: 0 -> 2 -> 3 -> 1 -> 4 -> 5, as now the distance will be 13, which is less than distance threshold. Look at graph below:

graph LR
	0 ---|10| 1
	0 ---|1| 2
	2 ---|1| 3
	1 ---|1| 3
	1 ---|1| 4
	4 ---|10| 5

linkStyle 1 stroke:green, stroke-width:4px
linkStyle 2 stroke:green, stroke-width:4px
linkStyle 3 stroke:green, stroke-width:4px

style 1 fill:#FF77FF
  

So, next time when we try the DFS, we go from 0 -> 2 -> 3-> 1, but as soon as we 1, we see it is already in visited set, so will never visit 5 because of that. So, DFS will not work. That is why we need Floyd Warshall Algorithm.

Method 1 - Floyd Warshall Algorithm

Floyd-Warshall is designed to find the shortest paths between all pairs of vertices in a graph, i.e. all-pairs shortest path. Read more: Floyd-Warshall Algorithm

So, to solve this problem, we can use the Floyd-Warshall algorithm to find the shortest paths between all pairs of cities. After computing the shortest paths, we can determine reachable cities within the given distance threshold and find the city with the smallest number of reachable cities. If there are ties, we return the city with the greatest number.

We can follow following steps:

1. Initialize the distance matrix: Set the initial distance between cities according to the given edges. If there is no direct edge, set the distance to infinity (inf). The distance from a city to itself is 0.
2. Floyd-Warshall Algorithm: Use this algorithm to compute the shortest paths between all pairs of cities.
3. Count reachable cities: For each city, count how many cities are reachable within the distanceThreshold.
4. Determine the result: Find the city with the smallest number of reachable cities. If there are ties, return the city with the greatest number.

Here is the video explanation:

Code

Java

public class Solution {

	public int findTheCity(int n, int[][] edges, int distanceThreshold) {
		// Initialize the distance matrix
		int[][] dist = new int[n][n];

		for (int i = 0; i < n; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
			dist[i][i] = 0; // Distance from a city to itself is 0
		}

		// Set initial distances based on the edges
		for (int[] edge: edges) {
			int from = edge[0];
			int to = edge[1];
			int weight = edge[2];
			dist[from][to] = weight;
			dist[to][from] = weight; // Since the graph is bidirectional
		}

		// Floyd-Warshall Algorithm to find the shortest paths between all pairs of cities
		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] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
					}
				}
			}
		}

		// Count reachable cities within distance threshold for each city
		int minReachable = n;
		int resultCity = -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 the number of reachable cities is smaller, or if the same but the city index is greater
			if (count < minReachable || (count == minReachable && i > resultCity)) {
				minReachable = count;
				resultCity = i;
			}
		}

		return resultCity;
	}
}

Complexity

• ⏰ Time complexity: O(n^3) where n is number of cities. This accounts for the triple nested loops required to update the shortest paths between all pairs of cities.
• 🧺 Space complexity: O(n^2), due to the 2D distance matrix.

Dry Run

Lets dry run the code for first eg. n = 4, edges =[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4

Initialize the distance matrix

Update Distances as per given edges

Run Floyd Warshall Algorithm

Use each node as an intermediate node (k) and update the shortest paths between all pairs of nodes (i and j).

k = 0

• For i = 0, j = 1, 2, 3: Distances remain the same since 0 is not providing any shorter path.
• For i = 1, j = 0, 2, 3: Distances remain the same since 0 is not providing any shorter path.
• Similarly for i = 2 and i = 3.

So, distance matrix stays the same.

k = 1

• For i = 0, j = 2: Consider path through 1, dist[0][2] = dist[0][1] + dist[1][2] = 3 + 1 = 4
• For i = 0, j = 3: Consider path through 1, dist[0][3] = dist[0][1] + dist[1][3] = 3 + 4 = 7
  • dist[0][3] = 7 (no change since initial value is inf)
• For i = 1, j = 3: No shorter path found through 1.
• Similarly for other combinations of i and j using k = 1.

Then, our distance matrix becomes:

k = 2

• For i = 0, j = 3: Consider path through 2:
  • dist[0][2] + dist[2][3] = 4 + 1 = 5
  • dist[0][3] = 5
• For i = 1, j = 3: No shorter path found through 2.
• Similarly for other combinations of i and j using k = 2.

Distance matrix after k = 2 iteration:

k = 3

• No additional updates as no shorter paths found through node 3.

So our distance matrix stays same. Now, we are done with floyd marshall algorithm.

Count Reachable Cities within Distance Threshold

For each city, count how many cities are reachable within distanceThreshold = 4.

City 0:

• Reachable cities: 0, 1, 2 ⇨ Count: 3

City 1:

• Reachable cities: 0, 1, 2, 3 ⇨ Count: 4

City 2:

• Reachable cities: 1, 2, 3 ⇨ Count: 4

City 3:

• Reachable cities: 1, 2, 3. ⇨ Count: 3

Final Result

Based on that we can either choose city 0 or city 3, but we choose city 3 as we have to choose node with larger value in case of tie.

Method 2 - Dijkstra’s Algorithm

Dijkstra’s Algorithm helps find shortest path from a single source vertex to all other vertices in a graph. But, here we have to find the shortest path from vertex to all vertices. So, we have to run the Dijkstra’s algorithm for all the vertices.

Here are the steps:

1. Graph Construction: An adjacency list is created to represent the bidirectional, weighted graph.
2. Dijkstra’s Algorithm:
   • For each city, Dijkstra’s algorithm is run to find the shortest path to all other cities within the distanceThreshold.
   • A priority queue (min-heap) is used to efficiently fetch the next closest city during the exploration of the graph.
3. Reachable Cities Count:
   • For each city, count of reachable cities within the distanceThreshold is computed.
   • Ensure to subtract 1 from the count to exclude the start city itself.
4. Finding the Result City:
   • Track the city with the smallest number of reachable cities, with ties broken by selecting the higher indexed city.

Code

Java

class Solution {

	public int findTheCity(int n, int[][] edges, int distanceThreshold) {
		// Create adjacency list
		List < int[] > [] graph = new ArrayList[n];

		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int[] edge: edges) {
			graph[edge[0]].add(new int[] {
				edge[1], edge[2]
			});
			graph[edge[1]].add(new int[] {
				edge[0], edge[2]
			}); // Since the graph is bidirectional
		}

		int minReachable = n;
		int resultCity = -1;

		for (int i = 0; i < n; i++) {
			int reachableCities = getReachableCitiesCount(i, graph, n, distanceThreshold);

			if (reachableCities <= minReachable) {
				if (reachableCities < minReachable || i > resultCity) { // Break tie by choosing the larger index
					minReachable = reachableCities;
					resultCity = i;
				}
			}
		}

		return resultCity;
	}

	private int getReachableCitiesCount(int start, List < int[] > [] graph, int n, int distanceThreshold) {
		PriorityQueue < int[] > pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		pq.offer(new int[] {
			start, 0
		});
		int[] distances = new int[n];
		Arrays.fill(distances, Integer.MAX_VALUE);
		distances[start] = 0;
		int reachableCities = 0;

		while (!pq.isEmpty()) {
			int[] current = pq.poll();
			int node = current[0];
			int dist = current[1];

			for (int[] neighbor: graph[node]) {
				int nextNode = neighbor[0];
				int weight = neighbor[1];

				if (dist + weight < distances[nextNode]) {
					distances[nextNode] = dist + weight;
					pq.offer(new int[] {
						nextNode, distances[nextNode]
					});
				}
			}
		}

		for (int dist: distances) {
			if (dist <= distanceThreshold) {
				reachableCities++;
			}
		}

		return reachableCities - 1; // Subtract 1 to exclude the start city itself
	}

}

Complexity

• ⏰ Time complexity: O(V*( (V+E) *log V)), Dijkstra’s algorithm, when using a priority queue, operates in O((V + E) log V), which is generally more efficient for denser graphs. We have to do it for V vertices.
• 🧺 Space complexity: O(NNNXXX)