Network Delay Time

Network Delay Time 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.

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), where E is the number of edges and N is the number of nodes. Building the adjacency list is O(E). Dijkstra's algorithm with a binary heap is O((E + N) log N) in the worst case, but since each edge is relaxed at most once, it's O(E log N). time and O(E + N), where E is the number of edges (for the adjacency list) and N is for the distance array and the priority queue. 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

Problems related to Network Delay Time

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.