Minimum Score of a Path Between Two Cities
MedPrompt
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] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. 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
1andnmultiple times along the path. - The test cases are generated such that there is at least one path between
1andn.
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 <= 1051 <= roads.length <= 105roads[i].length == 31 <= ai, bi <= nai != bi1 <= distancei <= 104- There are no repeated edges.
- There is at least one path between
1andn.
Approaches
2 approaches with complexity analysis and trade-offs.
The key insight is that since we can traverse any road multiple times, any path between two cities u and v can be extended to include any other road within the same connected component. This means the minimum score of a path between cities 1 and n is simply the minimum weight of any edge in the connected component that contains both 1 and n. We can find this component and the minimum edge weight by performing a graph traversal (like BFS or DFS) starting from city 1.
Algorithm
- Create an adjacency list
adjwhereadj[u]contains pairs of(v, distance)for each road betweenuandv. - Initialize a queue for BFS and add city
1. - Initialize a
visitedset or array and add1to it. - Initialize
minScore = Integer.MAX_VALUE. - While the queue is not empty:
- Dequeue the current city
u. - For each neighbor
vwith distancedfromu:- Update
minScore = min(minScore, d). - If
vhas not been visited, addvto the queue and thevisitedset.
- Update
- Dequeue the current city
- Return
minScore.
Walkthrough
We start by building an adjacency list representation of the graph from the roads array. Each entry in the adjacency list for a city u will store its neighbors and the distance to them.
We initialize a minScore variable to infinity and a visited array to keep track of the nodes we have already processed. We use a queue for a Breadth-First Search (BFS), starting with city 1.
In the BFS loop, we dequeue a city, and for each of its neighbors, we update minScore with the distance of the connecting road. If a neighbor hasn't been visited, we add it to the queue and mark it as visited.
The traversal continues until all reachable cities from city 1 have been visited. The final minScore will be the minimum edge weight in the entire connected component.
class Solution { public int minScore(int n, int[][] roads) { // 1. Build adjacency list Map<Integer, List<int[]>> adj = new HashMap<>(); for (int[] road : roads) { adj.computeIfAbsent(road[0], k -> new ArrayList<>()).add(new int[]{road[1], road[2]}); adj.computeIfAbsent(road[1], k -> new ArrayList<>()).add(new int[]{road[0], road[2]}); } int minScore = Integer.MAX_VALUE; boolean[] visited = new boolean[n + 1]; Queue<Integer> queue = new LinkedList<>(); // 2. Start BFS from city 1 queue.offer(1); visited[1] = true; while (!queue.isEmpty()) { int city = queue.poll(); if (!adj.containsKey(city)) { continue; } for (int[] neighborInfo : adj.get(city)) { int neighbor = neighborInfo[0]; int distance = neighborInfo[1]; // 3. Update minScore with every road in the component minScore = Math.min(minScore, distance); if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } return minScore; }}Complexity
Time
O(n + roads.length). Building the adjacency list takes `O(roads.length)`. The BFS traversal visits each node and edge in the connected component of city 1 at most once. In the worst case, the graph is fully connected, leading to `O(n + roads.length)` time.
Space
O(n + roads.length). The adjacency list requires `O(roads.length)` space. The `visited` array takes `O(n)` space, and the BFS queue can take up to `O(n)` space in the worst case.
Trade-offs
Pros
Conceptually straightforward, using a standard graph traversal algorithm.
Easy to implement.
Cons
Requires more space than the Union-Find approach due to the adjacency list, which can be significant if the number of roads is large.
Solutions
Solution
class Solution { private List < int []>[] g ; private boolean [] vis ; private int ans = 1 << 30 ; public int minScore ( int n , int [][] roads ) { g = new List [ n ]; vis = new boolean [ n ]; Arrays . setAll ( g , k -> new ArrayList <>()); for ( var e : roads ) { int a = e [ 0 ] - 1 , b = e [ 1 ] - 1 , d = e [ 2 ]; g [ a ]. add ( new int [] { b , d }); g [ b ]. add ( new int [] { a , d }); } dfs ( 0 ); return ans ; } private void dfs ( int i ) { for ( var nxt : g [ i ]) { int j = nxt [ 0 ], d = nxt [ 1 ]; ans = Math . min ( ans , d ); if (! vis [ j ]) { vis [ j ] = true ; dfs ( j ); } } } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.