Is Network Delay Time easy or hard?

Network Delay Time is classified as a Medium problem on LeetCode. The difficulty comes from recognizing the shortest path pattern and implementing Dijkstra’s algorithm correctly with a priority queue.

How to solve Network Delay Time in O(E log V)?

Build an adjacency list for the graph and run Dijkstra’s algorithm starting from node k. Use a min‑heap to repeatedly extract the node with the smallest current distance. Relax all outgoing edges and update neighbor distances when a shorter path is found.

What is the best approach for Network Delay Time?

Dijkstra’s algorithm with a min‑heap is the most efficient solution. It computes the shortest time from the source node to every other node in O(E log V) time. Because all edge weights are non‑negative, the greedy expansion of the nearest node guarantees optimal distances.

Is Network Delay Time asked at Google/Amazon/Meta?

Network Delay Time is a common graph interview problem and frequently appears in preparation lists for companies like Amazon, Google, and Meta. It tests understanding of shortest path algorithms, graph traversal, and priority queue usage.

What data structure is used in Network Delay Time?

The optimal solution uses an adjacency list to represent the graph and a min‑heap (priority queue) to select the next node with the smallest distance. A distance array tracks the shortest known travel time to each node.

What is the time complexity of Network Delay Time?

Using Dijkstra’s algorithm with a priority queue, the time complexity is O(E log V), where E is the number of edges and V is the number of nodes. The heap operations dominate the runtime while processing adjacency lists.

Network Delay Time Python or Java solution approach?

Python and C++ implementations typically use Dijkstra’s algorithm with a heap-based priority queue. Java and JavaScript solutions can also use Bellman‑Ford by iterating through all edges repeatedly to relax distances.

Description Hints 1 Solution Video 19:48

743. Network Delay Time

Medium61.7% acceptance9 companies

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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 <= u_i, v_i <= n
u_i != v_i
0 <= w_i <= 100
All the pairs (u_i, v_i) are unique. (i.e., no multiple edges.)

Asked at 9 companies

Akuna Capital NVIDIA Netflix

Google Salesforce Amazon Microsoft Bloomberg Meta

Topics

Hints open one at a time

Hint 1

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.

19:48

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution