LeetCode 2492 - Minimum Score of a Path Between Two Cities

The problem asks us to find the minimum possible score of a path between city 1 and city n in a graph defined by n cities and roads. Each road connects two cities bidirectionally and has an associated distance.

leetcodemediumdepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 2492

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks us to find the minimum possible score of a path between city 1 and city n in a graph defined by n cities and roads. Each road connects two cities bidirectionally and has an associated distance. The score of a path is defined as the minimum distance among all roads in that path. Unlike traditional shortest path problems where the total sum is considered, here we care about the smallest road in a path. The graph may contain cycles, and the path can revisit cities or roads multiple times. We are guaranteed that at least one path exists between city 1 and city n.

The input consists of:

  • n, the number of cities (up to 10^5)
  • roads, a list of road connections with distances (up to 10^5 entries)

The expected output is a single integer: the minimum possible score achievable along any path from city 1 to city n.

Key observations about constraints:

  • Cities are numbered from 1 to n, so indexing must account for this.
  • Distances are positive integers, so the minimum will always be ≥1.
  • Since there are no repeated edges, a simple adjacency list can be used.
  • The graph may not be fully connected, but a path between 1 and n exists, so we only need to consider the connected component containing city 1.

Edge cases include minimal graphs with two cities and one road, multiple paths with different minimal distances, and cycles that could influence the path selection if not handled carefully.

Approaches

Brute Force Approach

The brute-force approach would attempt to generate all possible paths between city 1 and city n, calculate the score for each path (the minimal distance along that path), and return the smallest score. This approach is correct in principle, but generating all paths in a graph with up to 10^5 nodes and 10^5 edges is computationally infeasible. Even using DFS to enumerate paths would lead to exponential time complexity, which is far beyond practical limits.

Optimal Approach

The key observation is that any path from city 1 to city n must stay within the connected component of city 1. Within this component, the minimum distance of any road encountered is a candidate for the minimum score. Therefore, we can explore the connected component using BFS or DFS and track the minimum distance of all edges encountered. There is no need to explicitly enumerate paths because every path is constrained by the edges in the component. The minimum edge in the component guarantees the minimum possible score along any path connecting 1 and n.

This approach reduces the problem to a graph traversal problem with a simple aggregation of edge weights, giving a linear time solution relative to the size of the graph.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Enumerate all paths, compute min per path
Optimal O(n + m) O(n + m) Traverse connected component, track min edge

Algorithm Walkthrough

  1. Build an adjacency list from the roads array. Each city maps to a list of tuples containing neighboring cities and the distance of the connecting road.
  2. Initialize a visited set to track cities already explored.
  3. Initialize a min_score variable with infinity to store the minimum distance seen.
  4. Perform BFS or DFS starting from city 1.
  5. For each city visited, iterate over its neighbors:
  • If the neighbor has not been visited, add it to the queue/stack.
  • Update min_score to be the minimum of the current min_score and the distance of the edge.
  1. Continue traversal until all cities reachable from 1 are visited.
  2. Return the min_score as the result.

Why it works: Any valid path from city 1 to city n must lie entirely within the connected component of city 1. Therefore, the minimum road in this component is guaranteed to be part of some path from 1 to n, making it the minimum possible score.

Python Solution

from typing import List
from collections import deque, defaultdict

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        # Build adjacency list
        graph = defaultdict(list)
        for a, b, distance in roads:
            graph[a].append((b, distance))
            graph[b].append((a, distance))
        
        visited = set()
        min_score = float('inf')
        queue = deque([1])
        visited.add(1)
        
        # BFS traversal
        while queue:
            node = queue.popleft()
            for neighbor, distance in graph[node]:
                min_score = min(min_score, distance)
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return min_score

Explanation: The adjacency list allows efficient lookups of neighboring cities. BFS ensures that all reachable cities are visited without infinite loops, using visited to track progress. During traversal, we maintain the smallest distance seen, which eventually gives the minimum score for any path from 1 to n.

Go Solution

package main

func minScore(n int, roads [][]int) int {
	graph := make([][][2]int, n+1)
	for _, road := range roads {
		a, b, dist := road[0], road[1], road[2]
		graph[a] = append(graph[a], [2]int{b, dist})
		graph[b] = append(graph[b], [2]int{a, dist})
	}

	visited := make([]bool, n+1)
	minScore := 1<<31 - 1

	queue := []int{1}
	visited[1] = true

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		for _, pair := range graph[node] {
			neighbor, dist := pair[0], pair[1]
			if dist < minScore {
				minScore = dist
			}
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}
	return minScore
}

Go Notes: We use slices of [2]int to store neighbors and distances. A boolean slice tracks visited cities. The BFS queue is managed with slice operations, and minScore uses a high initial value to track the minimum distance.

Worked Examples

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

Step Queue Visited min_score
Initialize [1] {1} inf
Visit 1 [2,4] {1,2,4} 7 (edge 1-4)
Visit 2 [4,3] {1,2,3,4} 5 (edge 2-4)
Visit 4 [3] {1,2,3,4} 5
Visit 3 [] {1,2,3,4} 5

Output: 5

Example 2: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]

Step Queue Visited min_score
Initialize [1] {1} inf
Visit 1 [2,3] {1,2,3} 2 (edge 1-2)
Visit 2 [3] {1,2,3} 2
Visit 3 [4] {1,2,3,4} 2
Visit 4 [] {1,2,3,4} 2

Output: 2

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each city and each road is visited at most once in BFS
Space O(n + m) Adjacency list stores all edges, plus visited set and queue

The algorithm scales linearly with the size of the graph, suitable for n, m ≤ 10^5.

Test Cases

# Provided examples
assert Solution().minScore(4, [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]) == 5  # min score along path 1->2->4
assert Solution().minScore(4, [[1,2,2],[1,3,4],[3,4,7]]) == 2          # min score along path 1->2

# Edge cases
assert Solution().minScore(2, [[1,2,1]]) == 1  # minimal graph
assert Solution().minScore(3, [[1,2,3],[2,3,2],[1,3,4]]) == 2  # multiple paths, pick min
assert Solution().minScore(5, [[1,2,5],[2,3,4],[3,4,3],[4,5,2],[1,5,10]]) == 2  # min edge in path

# Path with cycles
assert Solution().minScore(