2492. Minimum Score of a Path Between Two Cities
Problem Description
In this problem, we are working with a graph that represents a system of cities and bidirectional roads connecting these cities. The graph is composed of n
cities, which are numbered from 1 to n
. The roads are represented by a 2D array roads
, where each element in the array is a trio [a, b, distance]
. This trio indicates that there is a road connecting city a
and city b
with a distance of distance
. It's important to note that the graph of cities may not be fully connected, meaning some cities may not have a direct path to others.
The "score" of a path in this graph is a little unique; rather than summing up the total distance or considering average distance, the score is defined as the minimum distance of any road in that particular path. Put another way, out of all the roads used in a path, the score is the distance of the shortest one among them.
Our goal is to determine the minimum possible score of a path between city 1 and city n
. A few rules apply to paths:
- A path is simply a sequence of roads connecting two cities; it may pass through intermediate cities.
- It is permissible for a path to include the same road more than once, if necessary.
- You can go through cities 1 and
n
multiple times to find the path with the optimal score. - There is at least one path between city 1 and city
n
in all test cases.
Ultimately, we want to compute the highest "weakest" road in the best path from city 1 to city n
.
Flowchart Walkthrough
To solve Leetcode 2492. Minimum Score of a Path Between Two Cities, let's use the Flowchart to identify the appropriate algorithm. Here's a detailed step-by-step analysis:
-
Is it a graph?
- Yes: The problem involves cities and paths between them, which can naturally be represented as a graph where cities are nodes and paths are edges.
-
Is it a tree?
- No: The graph described can have multiple paths between cities and is not necessarily a hierarchy, so it's not a tree.
-
Is the problem related to directed acyclic graphs (DAGs)?
- No: The question does not specify that the graph is acyclic or directed. It's about finding a path in a general graph.
-
Is the problem related to shortest paths?
- Yes: The objective is to find a path with the minimum score between two cities, which aligns with shortest path problems.
-
Is the graph weighted?
- Yes: The problem involves scoring paths, implying that edges have weights.
-
Dijkstra's Algorithm
- Since the graph is weighted and we're looking for the shortest path, Dijkstra's Algorithm becomes suitable for solving this problem. However, let's pretend this answer doesn't satisfy the condition to find a DFS-based approach. Ignore relying on Dijkstra's and continue on the flowchart for educational purposes.
-
Does the problem involve connectivity?
- No: While the problem involves connections, the key problem is not just about connectivity but finding an optimized path, which shifts our focus away from generalized connectivity solutions.
The steps derived from applying the flowchart suggest the use of Dijkstra's Algorithm for a weighted shortest path problem. However, if explicitly asked to use Depth-First Search (or if using Dijkstra's is somehow unsuitable due to characteristics not detailed in the problemāsay, negative weights or special conditions), one could modify DFS to handle priority decisions based on path scores. However, generally, Depth-First Search isn't inherently optimal for finding minimum path scores in weighted graphs without significant modifications. Hence, the flowchart directed us primarily towards Dijkstra's for this type of problem.
Intuition
To solve this problem, we can utilize Depth-First Search (DFS) to explore all possible paths from city 1 to city n
. As we perform DFS, we track the minimum distance encountered along the current path. Before starting DFS, we initialize the answer ans
with a value representing infinity (inf
), because we will be minimizing this score as we go along.
To apply DFS, we first create a defaultdict
of lists called g
, which will be our graph where the keys are city numbers and the values are lists of tuples representing connected cities alongside the respective distances. We also create a list vis
of boolean values, initialized to False
, that keeps track of the cities that have been visited to prevent revisiting them in the current path exploration.
Our DFS process named dfs()
takes a city i
as an argument and iterates through all of its connections. For each adjacent city j
with distance d
to city i
, we minimize ans
with d
to find the smallest distance seen so far along this path segment. We also mark j
as visited and perform DFS from j
. The process recursively continues until we have exhausted all possible paths.
After initializing our data structures, we simply call dfs(1)
to start from the first city and allow the DFS to explore paths until city n
. Once DFS is done, the ans
variable will hold the minimum score among all paths from city 1 to city n
.
The solution is neat because it elegantly uses DFS to explore the space of paths, and it cleverly updates the minimum score on-the-fly. It relies on the fact that, since the score is the minimum distance along a path, we just need to track the smallest road distance encountered at any point in our DFS exploration.
Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.
Solution Approach
The implementation of the solution utilizes a Depth-First Search (DFS) algorithm which is a common strategy for exploring all the vertices of a graph. Let us walk through the important points of the implementation:
-
Graph Representation: A
defaultdict
of lists is used to represent the graph (g
). Each key in the defaultdict represents a city, and the value is a list of tuples. Each tuple consists of a destination city and the distance to that city. This allows us to easily iterate over all neighbors of a city. -
Visited Set: A list called
vis
is created with a size ofn + 1
, wheren
is the number of cities. The list is initialized withFalse
to indicate that no city has been visited at the start. This ensures that we do not enter into an infinite loop by revisiting cities during our DFS traversal. -
Distance Initialization: A variable
ans
is initialized withinf
(infinity). This variable is used to keep track of the minimum distance encountered on any path between city 1 and cityn
. -
DFS Algorithm: A recursive function
dfs(i)
is defined, which is responsible for traversing the graph:- Inside the DFS function, we iterate over each neighbor
j
and its associated distanced
of the current cityi
. - We update
ans
with the minimum of its current value andd
each time we encounter a smaller distance. - If the neighbor
j
has not yet been visited (vis[j]
isFalse
), we mark it as visited by settingvis[j]
toTrue
and then recursively calldfs(j)
to continue exploring the graph from cityj
.
- Inside the DFS function, we iterate over each neighbor
-
Starting the DFS Traversal: We call
dfs(1)
to begin our DFS traversal from city 1. This will explore different paths to reach cityn
. -
Result: Given that there is at least one path from city 1 to city
n
, by the end of DFS traversal,ans
will contain the minimum possible score (which is the minimum distance of the weakest road) in some path between city 1 and cityn
. Thisans
is then returned as a result.
The clever use of DFS allows for an efficient search through all the paths while keeping track of the minimum distance encountered, therefore the weakest link in terms of road distance, which effectively determines the score of the path.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example where n = 4
representing four cities and roads
as [[1, 2, 4], [2, 3, 3], [3, 4, 2], [1, 3, 6]]
. This setup implies the following connections:
- City 1 and city 2 are connected by a road with a distance of 4.
- City 2 and city 3 are connected by a road with a distance of 3.
- City 3 and city 4 are connected by a road with a distance of 2.
- City 1 and city 3 are directly connected as well with a distance of 6.
Following our solution approach:
-
Graph Representation: We first convert the
roads
array to a graph represented as adefaultdict
of lists,g
, so that we have:g = { 1: [(2, 4), (3, 6)], 2: [(1, 4), (3, 3)], 3: [(2, 3), (4, 2), (1, 6)], 4: [(3, 2)] }
Each list contains tuples that represent connections to neighboring cities and the distance to them.
-
Visited Set: We create
vis = [False, False, False, False, False]
. -
Distance Initialization: Set
ans = inf
. -
DFS Algorithm: For the
dfs
function, starting withdfs(1)
:- Look at neighbors of city 1: (2, 4) and (3, 6).
- For neighbor (2, 4), since city 2 is not visited, mark it visited and compare
ans
with 4.ans
becomes min(inf
, 4) = 4. - Continue DFS by calling
dfs(2)
.- In
dfs(2)
, iterate over neighbors: (1, 4) and (3, 3). - Skip city 1 since it's visited; for city 3 with distance 3, since city 3 is not visited, mark it visited and update
ans
to min(4, 3) = 3. - Continue DFS by calling
dfs(3)
.- In
dfs(3)
, check neighbors (2, 3), (4, 2), and (1, 6). - City 2 is visited, skip. Update
ans
with min(3, 2) when visiting city 4, soans
becomes 2. - City 4 has no unvisited neighbors left, so DFS goes back up.
- In
- In
This process continues until all possible paths between city 1 and city 4 have been explored through recursion.
-
Result: After the DFS is finished,
ans
holds the minimum distance encountered on any path, which in this case is 2. That means the highest "weakest" road on the best path from city 1 to city 4 has a distance of 2. This is the score of our path.
Hence, the minimum possible score for a path between city 1 and city 4 is 2, given this set of roads and cities.
Solution Implementation
1from collections import defaultdict
2from math import inf # Represents positive infinity
3
4class Solution:
5 def minScore(self, num_nodes: int, roads: List[List[int]]) -> int:
6 # Depth-First Search, where `current_node` is the current node being visited.
7 def dfs(current_node):
8 nonlocal minimum_road_score
9 for neighbor, road_score in graph[current_node]:
10 minimum_road_score = min(minimum_road_score, road_score)
11 if not visited[neighbor]:
12 visited[neighbor] = True
13 dfs(neighbor)
14
15 # Build graph representation from roads input.
16 graph = defaultdict(list)
17 for src, dest, score in roads:
18 graph[src].append((dest, score))
19 graph[dest].append((src, score))
20
21 # Initialize visited nodes list.
22 visited = [False] * (num_nodes + 1)
23
24 # Initialize the answer with infinity.
25 minimum_road_score = inf
26
27 # Start DFS from node 1 (assuming nodes are 1-indexed).
28 visited[1] = True
29 dfs(1)
30
31 # Return the minimum road score found during DFS.
32 return minimum_road_score
33
1class Solution {
2 private List<int[]>[] graph; // Graph represented as adjacency list
3 private boolean[] visited; // Visited array to keep track of visited nodes
4 private int minimumScore = Integer.MAX_VALUE; // Initialize minimum score to maximum possible value
5
6 // Function to find minimum score in the graph
7 public int minScore(int n, int[][] roads) {
8 graph = new List[n]; // Create graph with 'n' nodes
9 visited = new boolean[n]; // Initialize 'visited' array for 'n' nodes
10 // Fill the graph with empty lists for each node
11 Arrays.setAll(graph, k -> new ArrayList<>());
12 // Build the graph from the given roads information
13 for (int[] road : roads) {
14 int from = road[0] - 1; // Convert to 0-indexed
15 int to = road[1] - 1; // Convert to 0-indexed
16 int weight = road[2];
17 // Add edge to the undirected graph
18 graph[from].add(new int[] {to, weight});
19 graph[to].add(new int[] {from, weight});
20 }
21 // Start depth-first search traversal from node 0
22 dfs(0);
23 return minimumScore; // Return the minimum score found during DFS
24 }
25
26 // Helper function to perform depth-first search
27 private void dfs(int currentNode) {
28 // Go through all the connected nodes
29 for (int[] edge : graph[currentNode]) {
30 int nextNode = edge[0]; // Destination node
31 int weight = edge[1]; // Weight of the edge
32 // Update the minimum score encountered so far
33 minimumScore = Math.min(minimumScore, weight);
34 // If the next node is not visited, continue DFS traversal
35 if (!visited[nextNode]) {
36 visited[nextNode] = true; // Mark this node as visited
37 dfs(nextNode); // Recursively call dfs for the next node
38 }
39 }
40 }
41}
42
1#include <vector>
2#include <climits>
3#include <cstring>
4#include <functional>
5using namespace std;
6
7class Solution {
8public:
9 int minScore(int n, vector<vector<int>>& roads) {
10 // Create an adjacency list to represent the graph
11 vector<vector<pair<int, int>>> graph(n);
12 // Visited array to keep track of visited nodes
13 bool visited[n];
14 // Initialize the visited array to false for all nodes
15 memset(visited, 0, sizeof visited);
16
17 // Populate the adjacency list with road data
18 for (auto& road : roads) {
19 int from = road[0] - 1; // Convert to 0-based index
20 int to = road[1] - 1; // Convert to 0-based index
21 int distance = road[2];
22 graph[from].emplace_back(to, distance);
23 graph[to].emplace_back(from, distance);
24 }
25
26 // Initialize answer to maximum possible value
27 int answer = INT_MAX;
28
29 // Define the depth-first search (DFS) lambda function
30 function<void(int)> dfs = [&](int node) {
31 // Go through all edges connected to the current node
32 for (auto [adj_node, adj_distance] : graph[node]) {
33 // Update answer with the minimum distance so far
34 answer = min(answer, adj_distance);
35 // If adjacent node has not been visited
36 if (!visited[adj_node]) {
37 // Mark as visited
38 visited[adj_node] = true;
39 // Continue DFS from the adjacent node
40 dfs(adj_node);
41 }
42 }
43 };
44
45 // Start DFS from node 0 (converted to 0-based index previously)
46 visited[0] = true; // Mark node 0 as visited
47 dfs(0);
48
49 // Return the minimum score found by DFS
50 return answer;
51 }
52};
53
1function minScore(nodeCount: number, edges: number[][]): number {
2 // visited array to keep track of visited nodes
3 const visited = new Array(nodeCount + 1).fill(false);
4 // graph represented by an adjacency list
5 const graph = Array.from({ length: nodeCount + 1 }, () => []);
6
7 // Construct the graph from the given edges
8 for (const [nodeFrom, nodeTo, value] of edges) {
9 graph[nodeFrom].push([nodeTo, value]);
10 graph[nodeTo].push([nodeFrom, value]);
11 }
12
13 // Initialize answer with Infinity to find the minimum value later
14 let minimumScore = Infinity;
15
16 // Depth-first search to traverse the graph and find the minimum edge value
17 const depthFirstSearch = (currentNode: number) => {
18 // If the current node is already visited, skip it
19 if (visited[currentNode]) {
20 return;
21 }
22 // Mark the current node as visited
23 visited[currentNode] = true;
24 // Iterate over all neighbor nodes
25 for (const [nextNode, edgeValue] of graph[currentNode]) {
26 // Update the minimum score with the minimum edge value found so far
27 minimumScore = Math.min(minimumScore, edgeValue);
28 // Continue the search with the next node
29 depthFirstSearch(nextNode);
30 }
31 };
32
33 // Start the DFS from the first node (assuming nodes are labeled starting from 1)
34 depthFirstSearch(1);
35
36 // Return the minimum edge score found during the DFS
37 return minimumScore === Infinity ? -1 : minimumScore; // Return -1 if no edges were found
38}
39
40// Example usage:
41// const score = minScore(4, [[1, 2, 3], [2, 3, 1], [1, 3, 4]]);
42// console.log(score); // Output will be 1 which is the minimum edge value
43
Time and Space Complexity
Time Complexity
The given Python code implements a depth-first search (DFS) on a graph represented as a adjacency list. The dfs
function is called recursively to traverse the graph.
The time complexity of the algorithm depends on the number of nodes n
and the number of edges in the roads
list. The DFS will visit each node exactly once, due to the vis[j] = True
guard before each recursive call.
The complexity can have two major components: the time it takes to set up the adjacency list and the time it takes to do the DFS traversal.
-
Adjacency List Creation: The adjacency list is created by iterating through each road in the
roads
list. This operation takesO(E)
time whereE
is the number of edges as each edge is visited once. -
DFS Traversal: DFS traversal typically has a time complexity of
O(V + E)
for visiting each node and edge at most once.
Therefore the total time complexity is O(V + E)
where V
is the number of vertices and E
is the number of edges.
Space Complexity
The space complexity includes the storage for the graph (adjacency list), the visited array, and the stack space used by the recursive calls of DFS.
-
Graph Storage: Each node stores a list of its edges, so in total this is proportional to
O(E)
, whereE
is the number of edges. -
Visited Array: This is an array of length
n + 1
, thus taking upO(V)
space whereV
is the number of vertices. -
DFS Stack space: In the worst case, the recursive DFS could go as deep as the number of nodes in the graph (imagine a linked-list shaped graph), so the stack space in the worst case can be
O(V)
.
Consequently, the total space complexity is O(E + V)
with consideration for the adjacency list, visited array, and recursive stack space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Want a Structured Path to Master System Design Too? Donāt Miss This!