Minimum Score of a Path Between Two Cities

Medium

Asked by:

12 views

Topics:

GraphsGreedy Algorithms

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [a_i, b_i, distance_i] indicates that there is a bidirectional road between cities a_i and b_i with a distance equal to distance_i. The cities graph is not necessarily connected.

The score of a path between two cities is defined as the minimum distance of a road in this path.

Return the minimum possible score of a path between cities 1 and n.

Note:

A path is a sequence of roads between two cities.
It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
The test cases are generated such that there is at least one path between 1 and n.

Example 1:

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.

Example 2:

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.

Constraints:

2 <= n <= 10⁵
1 <= roads.length <= 10⁵
roads[i].length == 3
1 <= a_i, b_i <= n
a_i != b_i
1 <= distance_i <= 10⁴
There are no repeated edges.
There is at least one path between 1 and n.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of cities and roads that I should expect in the input?
Are the road distances guaranteed to be positive integers, or could they be zero or negative?
Is there guaranteed to be at least one path between city 1 and city n, and if not, what should I return?
Could there be multiple roads directly connecting the same two cities, and if so, should I consider all of them when determining the minimum score?
If there are multiple paths with the same minimum score, is any one of them acceptable?

Brute Force Solution

Approach

Imagine you're trying to find the route with the smallest road distance between two cities. The brute force method checks every possible route between the cities, no matter how long or winding. We'll look at each path individually to find the shortest road.

Here's how the algorithm would work step-by-step:

Start by listing all possible routes between the two cities. This includes routes that visit the same city multiple times.
For each route, find the smallest road distance on that specific route. This is like finding the 'weakest link' on that particular journey.
Now, compare the smallest road distances of all the routes you found.
The route with the absolute smallest road distance is the answer. That represents the minimum score for a path between the two cities.

Code Implementation

def find_minimum_score_brute_force(number_of_cities, roads):    # Represent the graph as an adjacency list.    graph = [[] for _ in range(number_of_cities + 1)]    for city_a, city_b, road_distance in roads:        graph[city_a].append((city_b, road_distance))        graph[city_b].append((city_a, road_distance))    all_paths = []    def find_all_paths(start_city, end_city, current_path, visited):        current_path.append(start_city)        visited[start_city] = True        if start_city == end_city:            all_paths.append(current_path[:])        else:            for neighbor, _ in graph[start_city]:                if not visited[neighbor]:                    find_all_paths(neighbor, end_city, current_path, visited)        current_path.pop()        visited[start_city] = False    # Find all paths from city 1 to city n.    visited = [False] * (number_of_cities + 1)    find_all_paths(1, number_of_cities, [], visited)
    minimum_score = float('inf')    # Iterate through all paths to find the minimum score.    for path in all_paths:        path_score = float('inf')        for i in range(len(path) - 1):            city_a = path[i]            city_b = path[i+1]            # Find the distance between two cities in the path.            for neighbor, road_distance in graph[city_a]:                if neighbor == city_b:                    path_score = min(path_score, road_distance)                    break        minimum_score = min(minimum_score, path_score)
    return minimum_score

Big(O) Analysis

Time Complexity

O(roads!) – The algorithm explores all possible paths between two cities. In the worst-case scenario, it might generate and evaluate all possible combinations of roads. The number of possible routes can grow factorially with the number of roads. Therefore, the time complexity is roughly proportional to the number of possible routes, which is O(roads!).

Space Complexity

O(N^N) – The algorithm explores all possible routes between two cities, potentially visiting the same city multiple times. In the worst-case scenario, with N cities, a route could visit each city, including repetitions, resulting in paths of length up to N. Since the algorithm lists *all* possible routes, and a route can be up to length N, the number of potential routes can grow as N to the power of N (N^N). Listing all those routes requires storing them in memory. Therefore, the space complexity is dominated by storing these potential paths, leading to O(N^N) auxiliary space.

Optimal Solution

Approach

The goal is to find the path between two cities that has the smallest, or 'minimum', road quality score. Instead of checking every single possible route, we'll use a method to efficiently explore the connections between cities, keeping track of the worst road we've seen so far.

Here's how the algorithm would work step-by-step:

Start at the first city.
Imagine exploring outwards from the first city, visiting all the cities directly connected to it.
As you explore, remember the score of each road you travel. Keep track of the *smallest* score you've seen on any of these roads.
Now, move to those connected cities and repeat the process: explore the cities connected to *them*, remembering to track the smallest road score you encounter. Make sure you only visit a city once to avoid going in circles.
Continue this exploration, always focusing on finding the smallest road score and systematically covering all reachable cities.
Once you reach the destination city, the smallest road score you've been tracking is the answer: the minimum score of a path between the two cities. If you can't reach the destination city, it means there's no path between them.

Code Implementation

def find_minimum_score(number_of_cities, roads):
    graph = [[] for _ in range(number_of_cities + 1)]
    for city_a, city_b, road_quality in roads:
        graph[city_a].append((city_b, road_quality))
        graph[city_b].append((city_a, road_quality))

    minimum_road_quality = float('inf')
    visited = [False] * (number_of_cities + 1)
    cities_to_visit = [1]
    visited[1] = True

    # Use BFS to traverse the graph
    while cities_to_visit:
        current_city = cities_to_visit.pop(0)

        # Explore all adjacent cities
        for neighbor_city, road_quality in graph[current_city]:
            minimum_road_quality = min(minimum_road_quality, road_quality)

            # Avoid cycles by only visiting unvisited cities
            if not visited[neighbor_city]:
                cities_to_visit.append(neighbor_city)
                visited[neighbor_city] = True

    return minimum_road_quality

Big(O) Analysis

Time Complexity

O(E + V) – The algorithm explores the graph using a breadth-first or depth-first search approach, where V represents the number of vertices (cities) and E represents the number of edges (roads). In the worst-case scenario, we visit each city and traverse each road once. Therefore, the time complexity is proportional to the sum of the number of edges and vertices, resulting in O(E + V).

Space Complexity

O(N) – The algorithm explores the connections between cities using a queue or stack (implicit in step 4), which can, in the worst case, hold all the cities if they are all reachable from the starting city. We also need a set to keep track of visited cities (step 4), which can also grow up to the number of cities. Therefore, the auxiliary space used is proportional to the number of cities, N. This implies a space complexity of O(N), where N represents the number of cities.

Edge Cases

Case	How to Handle
Null or empty roads array	Return -1 immediately as no path information exists.
roads array containing an empty road (e.g., [[]])	Treat such a road as invalid and skip it during processing; the problem statement should clarify if empty roads are possible, if not, throw an exception.
Only one city (n=1)	Return 0 immediately since there is no path between two distinct cities.
Disjoint graph: no path exists between city 1 and city n	The algorithm should return -1, or some other suitable indication that no path exists, after exploring all reachable nodes from city 1.
roads array containing invalid city numbers (e.g., city number > n)	Filter out or ignore any roads that refer to cities outside the valid range 1 to n, or throw an error.
roads array containing duplicate roads (same start, end, and distance)	The algorithm should treat these as the same road and not double-count them.
Very large distance values, potentially causing integer overflow during min calculations.	Use a 64-bit integer type or appropriate data type to avoid integer overflow during minimum distance calculations.
Roads with zero distance between cities.	Consider zero-distance roads during pathfinding, as they could be part of a path with the minimum overall score.

Null or empty roads array

How to Handle:

Return -1 immediately as no path information exists.

roads array containing an empty road (e.g., [[]])

How to Handle:

Treat such a road as invalid and skip it during processing; the problem statement should clarify if empty roads are possible, if not, throw an exception.

Only one city (n=1)

How to Handle:

Return 0 immediately since there is no path between two distinct cities.

Disjoint graph: no path exists between city 1 and city n

How to Handle:

The algorithm should return -1, or some other suitable indication that no path exists, after exploring all reachable nodes from city 1.

roads array containing invalid city numbers (e.g., city number > n)

How to Handle:

Filter out or ignore any roads that refer to cities outside the valid range 1 to n, or throw an error.

roads array containing duplicate roads (same start, end, and distance)

How to Handle:

The algorithm should treat these as the same road and not double-count them.

Very large distance values, potentially causing integer overflow during min calculations.

How to Handle:

Use a 64-bit integer type or appropriate data type to avoid integer overflow during minimum distance calculations.

Roads with zero distance between cities.

How to Handle:

Consider zero-distance roads during pathfinding, as they could be part of a path with the minimum overall score.