743. Network Delay Time
Network Delay Time (LeetCode 743) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.
How to solve Network Delay Time
Network Delay Time is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.
Work towards the solution in these steps:
- We visit each node at some time, and if that time is better than the fastest time we've reached this node, we travel along outgoing edges in sorted order. Alternatively, we could use Dijkstra's algorithm.
The reference solution runs in O(E + N log N) time and O(E + N) space.
The Network Delay Time solution and editorial walks through the full approach with reference code.
Problem statement
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.)
Topics and companies
Topics: Depth-First Search, Breadth-First Search, Graph, Heap (Priority Queue), Shortest Path.
Reported in interviews at Amazon.
How to practise Network Delay Time on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(E + N log N) time and O(E + N) space.
Open Network Delay Time in the code editor, or read the Network Delay Time editorial for a worked solution with its approach and complexity analysis.
Where Network Delay Time sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Shortest Path (Dijkstra's Algorithm) subpattern
- The full DSA patterns sheet
Problems related to Network Delay Time
Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:
- Find the Safest Path in a Grid — Medium, same subpattern
- Minimum Obstacle Removal to Reach Corner — Hard, same subpattern
- Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
- Minimum Weighted Subgraph With the Required Paths — Hard, same subpattern
- Number of Ways to Arrive at Destination — Medium, same subpattern
- Path with Maximum Probability — Medium, same subpattern
Network Delay Time FAQ
What is the LeetCode number of Network Delay Time?
Network Delay Time is LeetCode problem 743, rated Medium.
What pattern is used to solve Network Delay Time?
Network Delay Time is a Dijkstra's Algorithm for Shortest Path problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.
What is the time complexity of Network Delay Time?
The reference solution runs in O(E + N log N) time and O(E + N) space.
Which companies ask Network Delay Time?
Network Delay Time has been reported in interviews at Amazon.