We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

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 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.

Key Insights

  • The problem can be modeled as a graph where cities are nodes and edges represent weighted paths between them.
  • We need to find the number of reachable cities for each city within a certain distance threshold.
  • The Dijkstra's or Floyd-Warshall algorithm can be employed to find the shortest paths between cities efficiently.
  • If multiple cities have the same number of reachable neighbors, the city with the highest index should be returned.

Space and Time Complexity

Time Complexity: O(n^3) for Floyd-Warshall or O((n + e) log n) for Dijkstra's algorithm (where e is the number of edges)
Space Complexity: O(n^2) for Floyd-Warshall or O(n) for Dijkstra's algorithm using a priority queue

Solution

To solve the problem, we can use the Floyd-Warshall algorithm to compute the shortest paths between all pairs of cities. For each city, we count how many other cities can be reached within the given distance threshold. We then determine which city has the smallest count of reachable neighbors, returning the highest index city in case of ties.

  1. Initialize a distance matrix with infinity values, except for the diagonal (distance to itself is 0).
  2. Populate the distance matrix with the weights from the edges.
  3. Apply the Floyd-Warshall algorithm to calculate the shortest paths.
  4. For each city, count the number of reachable cities within the distance threshold.
  5. Track the city with the smallest count, preferring higher indices in case of ties.

Code Solutions

def findTheCity(n, edges, distanceThreshold):
    # Initialize the distance matrix
    inf = float('inf')
    dist = [[inf] * n for _ in range(n)]
    
    # Set the initial distances
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # Because the graph is undirected
    
    # Floyd-Warshall algorithm to find shortest paths
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # Count reachable cities within the distance threshold
    min_neighbors = inf
    city_with_min_neighbors = -1
    
    for i in range(n):
        count = sum(1 for j in range(n) if dist[i][j] <= distanceThreshold)
        if count < min_neighbors or (count == min_neighbors and i > city_with_min_neighbors):
            min_neighbors = count
            city_with_min_neighbors = i
            
    return city_with_min_neighbors
← Back to All Questions