Network Delay Time

Leetcode Link

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Solution

We wish to find the shortest path from k to all nodes in the graph. Dijkstra's algorithm is the best approach in finding shortest path from a single source. We will keep track of the delay time from k to each node, and find the maximum in the end.

Implementation

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for src, dst, time in times:
        graph[src].append((time, dst)) 
    
    queue = [(0, k)]
    delay_time = [inf for _ in range(n+1)]
    while queue:
        cur_time, cur_node = heapq.heappop(queue) # pop min from min-heap
        if cur_time > delay_time[cur_node]:       # a shorter path exists
            continue
        for edge in graph[cur_node]:
            new_time, new_node = edge
            if delay_time[new_node] > cur_time + new_time:
                delay_time[new_node] = cur_time + new_time
                heapq.heappush(queue, (delay_time[new_node], new_node))
    
    max_delay = max(delay_time)
    return max_delay if max_delay != inf else -1

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know

Network Delay Time

Solution

Implementation

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Recommended Readings