Problem Statement

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 and weighted edge between cities from(i), and to(i), and given the integer distance Threshold. Find out a city with smallest number of cities that reachable through some path and whose distance is at most Threshold Distance.

Examples

Example 1:

Input: N = 4, M = 4,
       edges = [
                [0, 1, 3],
                [1, 2, 1],
                [1, 3, 4],
                [2, 3, 1]
               ],
       distanceThreshold = 4

Output: 3

Explanation:
The adjacent cities for each city at a distnaceThreshold 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]

Here, City 0 and City 3 have a minimum number of cities i.e. 2 within distanceThreshold. So, the result will be the city with the largest number. So, the answer is City 3.

Example 2:

Input: N = 3, M = 2,
       edges = [
                [0, 1, 1],
                [0, 2, 3]
               ],
       distanceThreshold = 2
       
Output: 2

Explanation:
City 0 -> City 1
City 1 -> City 0
City 2 -> No City
Hence, the answer is 2.

Different Approaches

1️⃣ Floyd Warshall Algorithm

Intuition:

To find out which city is having the smallest number of cities that are reachable with at most Threshold distance, we firstly need to find the distance between every two pair of nodes(cities) possible then it can be compared with the threshold distance to get the answer.

In order to find the distance between every two pair of nodes, the Floyd Warshall Algorithm can be used. Once the 2D distance matrix(that contains the shortest paths) is generated, for each node(city), we can count the number of nodes(cities) that can be reached with a distance lesser or equal to the Threshold distance.

Approach:

1. Represent the cities and the bidirectional weighted edges using an adjacency matrix. Initialize all distances to a large value (infinity) except for the direct edges between cities.
2. Apply the Floyd-Warshall algorithm to compute the shortest paths between all pairs of cities. This algorithm iteratively updates the distance between any two cities through an intermediate city if it offers a shorter path.
3. For each city, count the number of cities that are reachable within the given distance threshold.
4. Identify the city with the smallest number of reachable cities within the threshold. If multiple cities have the same number of reachable cities, choose the city with the greater index.

Code:

class Solution {
public:
    int findCity(int n, int m, vector<vector<int>>& edges, int distanceThreshold) {

        // Step 1: Build the distance matrix.
        // Initialize an n x n matrix with a large value (infinity substitute, here 1e9) to represent unreachable distances.
        vector<vector<int>> matrix(n, vector<int>(n, 1e9));

        // Step 2: Populate the matrix with direct edge weights.
        // Iterate through all given edges.
        for (int i = 0; i < m; i++) {
            vector<int> edge = edges[i]; // each edge is in the format [u, v, wt]
            int u = edge[0];
            int v = edge[1];
            int wt = edge[2];

            // Since the graph is undirected, set both directions.
            matrix[u][v] = wt;
            matrix[v][u] = wt;
        }

        // Step 3: Apply the Floyd–Warshall algorithm to compute shortest paths between all pairs of cities.
        // 'via' represents the intermediate node used to update the shortest paths.
        for (int via = 0; via < n; via++) {
            // For each starting city i.
            for (int i = 0; i < n; i++) {
                // For each destination city j.
                for (int j = 0; j < n; j++) {
                    // If going from i to j via the 'via' node offers a shorter path, update the matrix.
                    matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j]);
                }
            }
        }

        // Step 4: Find the city with the smallest number of reachable neighbors within the distance threshold.
        int minCount = 1e9; // Use a large value as the initial minimum count.
        int city = -1;      // Initialize the city index to -1.

        // Iterate over each city (each row represents distances from that city to all others).
        for (int row = 0; row < n; row++) {
            int count = 0; // Counter for reachable cities from the current city.

            // Check the distance from the current city (row) to every other city (col).
            for (int col = 0; col < n; col++) {
                // Avoid counting the distance from a city to itself.
                if (row != col && matrix[row][col] <= distanceThreshold) {
                    count++;
                }
            }

            // If the current city has a count less than or equal to the current minimum, update the minimum and city.
            // This ensures that in a tie, the city with the greater index is chosen.
            if (count <= minCount) {
                minCount = count;
                city = row;
            }
        }

        // Return the index of the city that has the smallest number of reachable neighbors.
        return city;
    }
};

Complexity Analysis:

• Time Complexity:O(N^3) (where N is the number of nodes(cities) in graph)
  • The Floyd Warshall algorithm takes O(N^3) time to compute shortest distance between every pair of nodes.
  • Finding the city having smallest number of neighbors takes O(N^2) time.
• Space Complexity:O(N^2)
  • The only space used is for the distance matrix taking O(N^2) space and for a couple of variables taking O(1) space.