Minimum Score of a Path Between Two Cities

Med

#2274Time: 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.

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Graph

Prompt

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.

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 adj where adj[u] contains pairs of (v, distance) for each road between u and v.
Initialize a queue for BFS and add city 1.
Initialize a visited set or array and add 1 to it.
Initialize minScore = Integer.MAX_VALUE.
While the queue is not empty:
- Dequeue the current city u.
- For each neighbor v with distance d from u:
  - Update minScore = min(minScore, d).
  - If v has not been visited, add v to the queue and the visited set.
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.

1class Solution {2    public int minScore(int n, int[][] roads) {3        // 1. Build adjacency list4        Map<Integer, List<int[]>> adj = new HashMap<>();5        for (int[] road : roads) {6            adj.computeIfAbsent(road[0], k -> new ArrayList<>()).add(new int[]{road[1], road[2]});7            adj.computeIfAbsent(road[1], k -> new ArrayList<>()).add(new int[]{road[0], road[2]});8        }9 10        int minScore = Integer.MAX_VALUE;11        boolean[] visited = new boolean[n + 1];12        Queue<Integer> queue = new LinkedList<>();13 14        // 2. Start BFS from city 115        queue.offer(1);16        visited[1] = true;17 18        while (!queue.isEmpty()) {19            int city = queue.poll();20 21            if (!adj.containsKey(city)) {22                continue;23            }24 25            for (int[] neighborInfo : adj.get(city)) {26                int neighbor = neighborInfo[0];27                int distance = neighborInfo[1];28 29                // 3. Update minScore with every road in the component30                minScore = Math.min(minScore, distance);31 32                if (!visited[neighbor]) {33                    visited[neighbor] = true;34                    queue.offer(neighbor);35                }36            }37        }38 39        return minScore;40    }41}

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.

This approach also relies on the fact that the answer is the minimum edge weight in the connected component of city 1. The Union-Find data structure is highly optimized for determining connected components. We can first use it to group all cities into components by processing each road. Then, we can find the component city 1 belongs to and iterate through the roads again to find the minimum weight road that connects two cities within that component.

Algorithm

Initialize a DSU data structure for n cities.
For each road [u, v, d] in roads:
- Perform union(u, v).
Initialize minScore = Integer.MAX_VALUE.
Find the representative of city 1's component: root1 = find(1).
For each road [u, v, d] in roads:
- If find(u) is equal to root1, it means this road is in the same component.
- Update minScore = min(minScore, d).
Return minScore.

Walkthrough

We use a Disjoint Set Union (DSU) data structure, often implemented with a parent array, to keep track of the sets of connected cities.

First, we iterate through all the roads. For each road [u, v, distance], we perform a union operation on cities u and v. This merges the sets they belong to, effectively building the connected components of the graph.

After processing all roads, the DSU structure correctly represents the components. We then find the representative of the component containing city 1 using the find operation.

Finally, we iterate through the roads array one more time. For each road, we check if one of its cities belongs to the same component as city 1 (by comparing their representatives). If it does, we update our minScore with the distance of that road.

1class DSU {2    private int[] parent;3    public DSU(int n) {4        parent = new int[n + 1];5        for (int i = 1; i <= n; i++) {6            parent[i] = i;7        }8    }9 10    public int find(int i) {11        if (parent[i] == i) {12            return i;13        }14        return parent[i] = find(parent[i]); // Path compression15    }16 17    public void union(int i, int j) {18        int rootI = find(i);19        int rootJ = find(j);20        if (rootI != rootJ) {21            parent[rootJ] = rootI;22        }23    }24}25 26class Solution {27    public int minScore(int n, int[][] roads) {28        DSU dsu = new DSU(n);29        // 1. Build components30        for (int[] road : roads) {31            dsu.union(road[0], road[1]);32        }33 34        int minScore = Integer.MAX_VALUE;35        // 2. Find min edge in the component of city 136        for (int[] road : roads) {37            if (dsu.find(1) == dsu.find(road[0])) {38                minScore = Math.min(minScore, road[2]);39            }40        }41 42        return minScore;43    }44}

Complexity

Time

O(n + roads.length * α(n)), where `α(n)` is the inverse Ackermann function. Initializing the DSU takes `O(n)`. The first loop performs `roads.length` union operations, and the second loop performs `roads.length` find operations. With path compression, these operations take nearly constant time on average, `O(α(n))`.

Space

O(n). The DSU data structure requires a `parent` array of size `n`, leading to `O(n)` space. This is more efficient than the BFS/DFS approach if the number of roads is large.

Trade-offs

Pros

Excellent space efficiency, using only O(n) space.
Very fast, with nearly linear time complexity.

Cons

Requires two passes over the roads data.
The DSU data structure might be slightly less intuitive than a simple graph traversal for some.

Solutions

Solution

1class 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 ); } } } }

1var minScore = function ( n , roads ) { // 构建点到点的映射表 const graph = Array . from ({ length : n + 1 }, () => new Map ()); for ( let [ u , v , w ] of roads ) { graph [ u ]. set ( v , w ); graph [ v ]. set ( u , w ); } // DFS const vis = new Array ( n ). fill ( false ); let ans = Infinity ; var dfs = function ( u ) { vis [ u ] = true ; for ( const [ v , w ] of graph [ u ]) { ans = Math . min ( ans , w ); if ( ! vis [ v ]) dfs ( v ); } }; dfs ( 1 ); return ans ; };

1class Solution { public: int minScore ( int n , vector < vector < int >>& roads ) { vector < vector < pair < int , int >>> g ( n ); bool vis [ n ]; memset ( vis , 0 , sizeof vis ); for ( auto & e : roads ) { int a = e [ 0 ] - 1 , b = e [ 1 ] - 1 , d = e [ 2 ]; g [ a ]. emplace_back ( b , d ); g [ b ]. emplace_back ( a , d ); } int ans = INT_MAX ; function < void ( int ) > dfs = [ & ]( int i ) { for ( auto [ j , d ] : g [ i ]) { ans = min ( ans , d ); if ( ! vis [ j ]) { vis [ j ] = true ; dfs ( j ); } } }; dfs ( 0 ); return ans ; } };

1class Solution : def minScore ( self , n : int , roads : List [ List [ int ]]) -> int : def dfs ( i ): nonlocal ans for j , d in g [ i ]: ans = min ( ans , d ) if not vis [ j ]: vis [ j ] = True dfs ( j ) g = defaultdict ( list ) for a , b , d in roads : g [ a ]. append (( b , d )) g [ b ]. append (( a , d )) vis = [ False ] * ( n + 1 ) ans = inf dfs ( 1 ) return ans

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.

← Previous

Previous problem

Next problem