How do you solve Minimum Score of a Path Between Two Cities?

Build an adjacency list representation of the graph. Use DFS starting from city 1 to visit all reachable nodes. During traversal, track the minimum edge score encountered. Since the graph is connected, the DFS will reach city n, and the global minimum edge score found during traversal is the minimum score of any path between city 1 and city n.

What pattern does Minimum Score of a Path Between Two Cities use?

The Pattern: DFS (Graph Connectivity and State Propagation) The Heuristic: When the problem requires aggregating a property (like minimum edge weight) over all nodes reachable from a source in an undirected graph, a DFS traversal that propagates and updates a global state efficiently captures the solution without enumerating all paths.

Minimum Score of a Path Between Two Cities — DFS

Q: What is the time complexity of Minimum Score of a Path Between Two Cities?

O(n + m). Building the adjacency list takes O(m) time, where m is the number of roads. DFS visits each node and edge once, resulting in O(n + m) total time.

Problem

Given n cities numbered from 1 to n and a list of roads where each road connects two cities with a certain score, return the minimum score of any path between city 1 and city n. You may assume the graph is connected and the path can revisit cities and roads multiple times.

2 ≤ n ≤ 10⁵
1 ≤ roads.length ≤ 10⁵
roads[i].length == 3
1 ≤ a_i, b_i ≤ n
1 ≤ score_i ≤ 10⁴
There is at least one path between city 1 and city n

Example

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]

Output: 5

The graph has edges with scores 9, 6, 5, and 7. The path from city 1 to city 4 can be direct with score 7, or via city 2 and 4 with edges 9 and 5. The minimum score along the path 1->2->4 is min(9,5) = 5, which is less than the direct edge 7. The algorithm uses DFS starting from city 1 to explore all reachable nodes, tracking the minimum edge score encountered. The critical moment is when the DFS visits edge (2,4) with score 5, updating the global minimum score to 5. Since the graph is connected, DFS visits all nodes reachable from city 1, ensuring the minimum edge score on any path to city n is found.

Approach

Straightforward Solution

A brute-force approach would enumerate all paths from city 1 to city n and compute the minimum edge score for each, then take the minimum among these. This is computationally infeasible due to exponential path counts.

Core Observation

The minimum score of a path between two cities is the smallest edge weight on any path connecting them. Since the graph is connected, all nodes reachable from city 1 can be explored, and the minimum edge score among all edges in the connected component containing city 1 is the answer.

Path to Optimal

Preview

Recognizing that the minimum edge score on any path from city 1 to city n must be at least the minimum edge in the connected component of city 1, the problem reduces to finding the minimum edge weight in that component…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an adjacency list representation of the graph. Use DFS starting from city 1 to visit all reachable nodes…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Building the adjacency list takes O(m) time, where m is the number of roads. DFS visits each node and edge once, resulting in O(n + m) total time.

Space

O(n + m)

The adjacency list requires O(n + m) space. The recursion stack in DFS can go up to O(n) in the worst case. The visited set also uses O(n) space. This auxiliary space is necessary to track visited nodes and graph structure.

Solution

Python

1class Solution:
  def minScore(self, n: int, roads: List[List[int]]) -> int:
      graph = defaultdict(list)
4
      for a, b, w in roads:
          graph[a].append((b, w))
          graph[b].append((a, w))
8
      visited = set()
      res = float("inf")
11
      def dfs(node):
          nonlocal res
          visited.add(node)
15
          for nei, w in graph[node]:
              res = min(res, w)
              if nei not in visited:
                  dfs(nei)
20
      dfs(1)
      return res

Step-by-Step Solution

1

Construct the Undirected Graph as an Adjacency List

3graph = defaultdict(list)
5for a, b, w in roads:
6    graph[a].append((b, w))
7    graph[b].append((a, w))

Objective

To represent the road network efficiently for traversal by building an adjacency list mapping each city to its neighbors and edge scores.

Key Insight

An adjacency list allows O(1) average-time access to neighbors of any node and is space-efficient for sparse graphs. Representing the graph as undirected requires adding each edge in both directions, ensuring traversal can proceed from any node to its connected neighbors.

Interview Quick-Check

Core Logic

Building the adjacency list with bidirectional edges ensures the graph accurately models the undirected road network.

Common Pitfalls & Bugs

Forgetting to add edges in both directions leads to incomplete traversal and incorrect results.

2

Initialize Visited Set and Result Variable

To prepare tracking structures for DFS traversal and to store the minimum edge score found during exploration.

3

Traverse Graph with DFS to Update Minimum Edge Score

To recursively explore all nodes reachable from city 1, updating the global minimum edge score with each edge encountered.

4

Invoke DFS from City 1 and Return the Minimum Score

To start the DFS traversal from city 1 and return the minimum edge score found after full exploration.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 17 Critical

res = min(res, w)

Update the global minimum edge score with the current edge weight.

This line is the core of the algorithm: it continuously tracks the smallest edge weight encountered during traversal, which directly determines the minimum score of any path between city 1 and city n.

Line 13 Critical

nonlocal res

Declare res as nonlocal to update global minimum edge score.

Using nonlocal allows the recursive DFS calls to update the shared minimum edge score variable, maintaining state across recursion levels.

Line 21 Critical

dfs(1)

Start DFS traversal from city 1.

Initiating DFS at city 1 guarantees exploration of all nodes reachable from city 1, including city n, ensuring the minimum edge score is found.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does traversing the connected component of city 1 and tracking the minimum edge score guarantee the minimum score of any path to city n?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Score of a Path Between Two Cities from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Score of a Path Between Two Cities drill

or drill a free problem

1	`class Solution:`
2	`def minScore(self, n: int, roads: List[List[int]]) -> int:`
3	`graph = defaultdict(list)`
4
5	`for a, b, w in roads:`
6	`graph[a].append((b, w))`
7	`graph[b].append((a, w))`
8
9	`visited = set()`
10	`res = float("inf")`
11
12	`def dfs(node):`
13	`nonlocal res`
14	`visited.add(node)`
15
16	`for nei, w in graph[node]:`
17	`res = min(res, w)`
18	`if nei not in visited:`
19	`dfs(nei)`
20
21	`dfs(1)`
22	`return res`

3	`graph = defaultdict(list)`
5	`for a, b, w in roads:`
6	`graph[a].append((b, w))`
7	`graph[b].append((a, w))`