Network Delay Time
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
1def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
2 graph = defaultdict(list)
3 for src, dst, time in times:
4 graph[src].append((time, dst))
5
6 queue = [(0, k)]
7 delay_time = [inf for _ in range(n+1)]
8 while queue:
9 cur_time, cur_node = heapq.heappop(queue) # pop min from min-heap
10 if cur_time > delay_time[cur_node]: # a shorter path exists
11 continue
12 for edge in graph[cur_node]:
13 new_time, new_node = edge
14 if delay_time[new_node] > cur_time + new_time:
15 delay_time[new_node] = cur_time + new_time
16 heapq.heappush(queue, (delay_time[new_node], new_node))
17
18 max_delay = max(delay_time)
19 return max_delay if max_delay != inf else -1
Which algorithm should you use to find a node that is close to the root of the tree?
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Solution Implementation
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.