LeetCode Solutions Blog

Minimum Score of a Path Between Two Cities

Number: 2582

Difficulty: Medium

Paid? No

Problem Description

We are given n cities labeled from 1 to n and a list of bidirectional roads, where each road connects two cities with a certain distance. A path’s score is defined by the minimum distance among all roads used in that path. The objective is to find the minimum possible score along any path between city 1 and city n.

Key Insights

The score of a path is determined by the smallest edge (distance) along that path.
Instead of finding all paths from 1 to n, we recognize that the answer is the smallest road in the connected component reachable from city 1.
Traversing the connected component using DFS or BFS and keeping track of the minimum encountered distance is sufficient.
Union-Find is an alternative approach but graph traversal is more straightforward.

Space and Time Complexity

Time Complexity: O(n + m) where m is the number of roads, since every city and road is processed once. Space Complexity: O(n + m) due to the adjacency list representation and auxiliary data structures used for traversal.

Solution

We build an adjacency list for the graph and use a breadth-first search (BFS) starting from city 1 to explore the connected component that includes city 1. As we traverse each road, we continuously update the minimum distance found. This minimum value is the answer, because any path from 1 to n must lie within the connected component and will include at least one of these roads.

Code Solutions

# Import deque for an efficient FIFO implementation for BFS
from collections import defaultdict, deque

def minScore(n, roads):
    # Create an adjacency list to map each city to its neighbors with the respective road distance.
    graph = defaultdict(list)
    for city1, city2, distance in roads:
        graph[city1].append((city2, distance))
        graph[city2].append((city1, distance))
    
    # Initialize a visited set to keep track of cities we have processed during the BFS.
    visited = set()
    # Use deque as our queue for BFS starting with city 1.
    queue = deque([1])
    visited.add(1)
    
    # Initialize the answer with infinity.
    min_score = float('inf')
    
    # BFS: iterate until the queue is empty.
    while queue:
        city = queue.popleft()
        # Check every adjacent city and its road distance
        for neighbor, distance in graph[city]:
            # Update the minimum road distance encountered.
            min_score = min(min_score, distance)
            # If the neighbor has not been visited, add it to the visited set and queue.
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return min_score

# Example usage:
n = 4
roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
print(minScore(n, roads))  # Expected output: 5