Skip to main content
Talentd

Minimum Score of a Path Between Two Cities - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchUnion FindGraph24 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

Problem Statement

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 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 <= 105
  • 1 <= roads.length <= 105
  • roads[i].length == 3
  • 1 <= ai, bi <= n
  • ai != bi
  • 1 <= distancei <= 104
  • There are no repeated edges.
  • There is at least one path between 1 and n.

Approach Overview

Problem Overview: You are given n cities connected by bidirectional roads with weights. The score of a path is defined as the minimum edge weight along that path. The goal is to find the minimum possible score of any path between city 1 and city n.

The key observation: since the graph is undirected and you can revisit cities, any path between two nodes in the same connected component can potentially include any edge in that component. That means the answer becomes the smallest edge weight in the connected component containing both city 1 and city n.

Approach 1: BFS / DFS Traversal (O(n + m) time, O(n + m) space)

Build an adjacency list for the graph and run a traversal starting from city 1. During traversal, visit all reachable cities and keep track of the minimum road weight encountered. Each time you iterate over neighbors, update the global minimum using min(ans, weight). Because all nodes reachable from city 1 belong to the same connected component, this traversal effectively scans every road that could appear in a valid path between city 1 and city n. This approach is straightforward and works well when you already represent the graph using adjacency lists.

Both Breadth-First Search and Depth-First Search work here. BFS uses a queue and explores level by level, while DFS uses recursion or a stack. Since the goal is simply to explore the connected component, either traversal produces the same result.

Approach 2: Union-Find (Disjoint Set Union) (O(m α(n)) time, O(n) space)

Use the Union-Find data structure to group cities into connected components. Iterate through all roads and union their endpoints. After building the sets, identify the root of city 1. Then iterate over all roads again and check whether both endpoints belong to this component. For every such road, update the minimum edge weight. The smallest weight among these roads becomes the path score.

This approach works because Union-Find quickly determines whether two nodes belong to the same component. With path compression and union by rank, each operation runs in nearly constant time O(α(n)).

Recommended for interviews: BFS or DFS traversal is usually the fastest to explain and implement during interviews. It directly explores the connected component of city 1 and tracks the smallest edge weight in O(n + m) time. Union-Find demonstrates stronger knowledge of graph connectivity structures and scales well when you repeatedly query components. Showing the traversal first proves understanding of graph connectivity, while the Union-Find optimization highlights deeper problem-solving skills.

Approach 1: Using Union-Find Data Structure

This approach involves using the Union-Find data structure (also known as Disjoint Set Union, DSU) to manage connections between cities efficiently. By iterating over all roads, we determine which cities are interconnected. The key is to keep track of the minimum weight of a road that connects these cities after they are all unified.

This solution utilizes an efficient means of finding and unifying elements, reducing the overhead of nested loops and allowing operations near constant-time with path compression and union by rank techniques.

This solution uses a Disjoint Set Union (DSU) to identify all the cities that are connected together. It then iterates over the connections (roads), linking them up, and finally examines the edges to find the smallest possible score afterward.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(E log* V)
Space Complexity: O(V)

Try this approach in the editor →

Approach 2: BFS/DFS Traversal

Another intuitive approach is to use graph traversal techniques such as BFS or DFS. Starting from city 1, you can explore all reachable cities while dynamically updating the minimum edge encountered during the exploration. This ensures you calculate the smallest score path by evaluating all potential paths to the destination city.

This C code uses DFS with an array of lists to store adjacent nodes. During DFS traversal, it keeps track of the minimum-weight edge to ensure the minimum score path is calculated.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(V + E)
Space Complexity: O(V + E)

Try this approach in the editor →

Approach 3: DFS

According to the problem description, each edge can be passed multiple times, and it is guaranteed that node 1 and node n are in the same connected component. Therefore, the problem is actually looking for the smallest edge in the connected component where node 1 is located. We can use DFS, start searching from node 1, and find the smallest edge.

The time complexity is O(n + m), where n and m are the number of nodes and edges, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: BFS

We can also use BFS to solve this problem.

The time complexity is O(n + m), where n and m are the number of nodes and edges, respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Union-Find Data Structure

Time Complexity: O(E log* V)
Space Complexity: O(V)

BFS/DFS Traversal

Time Complexity: O(V + E)
Space Complexity: O(V + E)

DFS—
BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS TraversalO(n + m)O(n + m)Best when using adjacency lists and exploring connected components
DFS TraversalO(n + m)O(n + m)Good for recursive exploration of graph components
Union-Find (Disjoint Set)O(m α(n))O(n)Useful when tracking connectivity across many edges or repeated component checks

Video Solution

Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python • NeetCodeIO • 15,117 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Score of a Path Between Two Cities easy or hard?
The problem is classified as Medium on LeetCode. The challenge is recognizing that the answer equals the smallest edge weight in the connected component containing city 1. Once that insight is clear, a simple BFS, DFS, or Union-Find implementation solves it efficiently.
Minimum Score of a Path Between Two Cities Python or Java solution?
Python and Java implementations typically use an adjacency list with BFS or DFS to traverse the graph. A variable tracks the smallest edge weight seen while visiting neighbors. The algorithm runs in O(n + m) time and requires O(n + m) space for the graph representation.
How to solve Minimum Score of a Path Between Two Cities in O(n + m)?
Construct an adjacency list and run BFS or DFS starting from city 1. While traversing neighbors, continuously update a variable storing the minimum road weight encountered. Since traversal covers the entire connected component of city 1, the smallest weight seen during exploration represents the minimum score of any valid path to city n.
What is the best approach for Minimum Score of a Path Between Two Cities?
The most practical approach is BFS or DFS traversal starting from city 1. Explore the entire connected component and track the smallest edge weight encountered. Since any path between city 1 and city n must stay inside this component, the minimum edge weight found during traversal becomes the answer. This runs in O(n + m) time.
Is Minimum Score of a Path Between Two Cities asked at Google/Amazon/Meta?
Graph connectivity and minimum edge problems are common in interviews at companies like Amazon, Google, and Meta. This problem specifically tests understanding of graph traversal and connected components using BFS, DFS, or Union-Find. Variations of this concept appear frequently in system design and algorithm interviews.
What data structure is used in Minimum Score of a Path Between Two Cities?
The problem primarily uses graph data structures such as adjacency lists for BFS or DFS traversal. Another common structure is Union-Find (Disjoint Set Union), which efficiently groups nodes into connected components and checks whether cities belong to the same set.
What is the time complexity of Minimum Score of a Path Between Two Cities?
The optimal solution runs in O(n + m) time where n is the number of cities and m is the number of roads. BFS or DFS visits each node and edge once while tracking the minimum weight. The Union-Find solution runs in O(m α(n)) due to nearly constant-time union and find operations.

Ready to solve this problem?

Practice Minimum Score of a Path Between Two Cities with our built-in code editor and test cases.

Practice on FleetCode
Previous

Checking Existence of Edge Length Limited Paths

Next

Checking Existence of Edge Length Limited Paths II