Network Delay Time

Problem

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 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.

Examples

Example 1:

flowchart LR
    classDef startNode fill:#ffefc6,stroke:#e07a5f,stroke-width:2px;
    2((2)):::startNode
    1((1))
    3((3))
    4((4))

    2 -->|1| 1
    2 -->|1| 3
    3 -->|1| 4

    %% labels for clarity
    subgraph key[Start node = 2]
    end

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

Variant 1 - Message Propagation Time (Daily Coding Problem 270)

This variant represents the same core problem with a slightly different presentation, corresponding to Daily Coding Problem 270 asked by Twitter.

A network consists of nodes labeled 0 to N. You are given a list of edges (a, b, t), describing the time t it takes for a message to be sent from node a to node b. Whenever a node receives a message, it immediately passes the message on to a neighboring node, if possible.

Assuming all nodes are connected, determine how long it will take for every node to receive a message that begins at node 0.

Example for Variant:

Input: N = 5, edges = [(0, 1, 5), (0, 2, 3), (0, 5, 4), (1, 3, 8), (2, 3, 1), (3, 5, 10), (3, 4, 5)]
Output: 9
Explanation: The optimal path is 0 -> 2 -> 3 -> 4, taking 3 + 1 + 5 = 9 time units.

Key Differences from Main Problem:

• Input format: Edges as tuples (a, b, t) instead of nested arrays
• Node numbering: Uses 0 to N instead of 1 to n
• Starting node: Always starts from node 0 instead of parameter k
• Assumptions: States "all nodes are connected" so no need to check for unreachable nodes

Solution

Method 1 – Dijkstra's Algorithm (BFS with Priority Queue)

Intuition

We need to find the shortest path from a given node to all other nodes. This is a classic shortest path problem that can be solved using Dijkstra's algorithm. The key insight is that we want to find the maximum time among all shortest paths, as this represents when the last node receives the signal.

Approach

1. Build an adjacency list representation of the graph
2. Use Dijkstra's algorithm with a priority queue (min-heap) to find shortest paths
3. Start from the given node k and explore neighbors with shortest distances first
4. Keep track of visited nodes and the maximum time taken
5. If all nodes are visited, return the maximum time; otherwise return -1

Code

C++

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int,int>>> g(n+1);
        for (auto& t : times) g[t[0]].emplace_back(t[1], t[2]);
        vector<bool> vis(n+1, false);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.emplace(0, k);
        int ans = 0, cnt = 0;
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = true; ans = d; cnt++;
            for (auto& [v, w] : g[u]) if (!vis[v]) pq.emplace(d+w, v);
        }
        return cnt == n ? ans : -1;
    }
};

Go

import "container/heap"

type Item struct { dist, node int }
type PQ []Item
func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PQ) Pop() interface{} {
    old := *pq; n := len(old); item := old[n-1]; *pq = old[0:n-1]; return item
}

func networkDelayTime(times [][]int, n int, k int) int {
    g := make([][]struct{to, w int}, n+1)
    for _, t := range times { g[t[0]] = append(g[t[0]], struct{to, w int}{t[1], t[2]}) }
    vis := make([]bool, n+1)
    pq := &PQ{{0, k}}
    heap.Init(pq)
    ans, cnt := 0, 0
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(Item)
        if vis[cur.node] { continue }
        vis[cur.node] = true; ans = cur.dist; cnt++
        for _, e := range g[cur.node] {
            if !vis[e.to] { heap.Push(pq, Item{cur.dist + e.w, e.to}) }
        }
    }
    if cnt == n { return ans }
    return -1
}

Java

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) graph.put(i, new HashMap<>());
        for (int[] time : times) graph.get(time[0]).put(time[1], time[2]);
        
        Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[]{0, k});
        boolean[] vis = new boolean[n + 1];
        int ans = 0;
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (vis[u]) continue;
            vis[u] = true; ans = d;
            for (var entry : graph.get(u).entrySet()) {
                int v = entry.getKey(), w = entry.getValue();
                if (!vis[v]) pq.add(new int[]{d + w, v});
            }
        }
        
        for (int i = 1; i <= n; i++) if (!vis[i]) return -1;
        return ans;
    }
}

Python

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = defaultdict(list)
        for u, v, w in times:
            g[u].append((v, w))
        
        vis = set()
        pq = [(0, k)]
        ans = 0
        
        while pq:
            d, u = heapq.heappop(pq)
            if u in vis:
                continue
            vis.add(u)
            ans = d
            for v, w in g[u]:
                if v not in vis:
                    heapq.heappush(pq, (d + w, v))
        
        return ans if len(vis) == n else -1

TypeScript

function networkDelayTime(times: number[][], n: number, k: number): number {
    const g = new Map<number, Map<number, number>>();
    for (let i = 1; i <= n; i++) g.set(i, new Map());
    for (const [u, v, w] of times) g.get(u)!.set(v, w);
    
    const pq: [number, number][] = [[0, k]];
    const vis = new Set<number>();
    let ans = 0;
    
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift()!;
        if (vis.has(u)) continue;
        vis.add(u); ans = d;
        for (const [v, w] of g.get(u) ?? []) {
            if (!vis.has(v)) pq.push([d+w, v]);
        }
    }
    return vis.size === n ? ans : -1;
}

Complexity

• ⏰ Time complexity: O(E log N) where E is the number of edges and N is the number of nodes (for Dijkstra's algorithm).
• 🧺 Space complexity: O(N + E) for the graph and visited structures.

Solution for Variant 1 - Message Propagation Time

Method 1 - Reuse the method1 in previous solution

Since this is essentially the same problem with different input format and starting node, we can reuse the original networkDelayTime solution by simply converting the input format and setting k = 0.

Key Implementation Notes

1. Input Conversion: Convert tuple format (a, b, t) to array format [a, b, t]
2. Node Count Adjustment: Use N + 1 as the total node count since nodes are labeled 0 to N
3. Starting Node: Set k = 0 to start from node 0
4. Code Reuse: Leverage the existing optimized Dijkstra's implementation

Complexity

• ⏰ Time complexity: O(E log N) - Same as main problem
• 🧺 Space complexity: O(N + E) - Same as main problem

This elegant solution demonstrates how problem variants can often be solved by simple input/output transformations rather than rewriting the entire algorithm.

Code

C++

class Solution {
public:
    int messageDelayTime(vector<tuple<int,int,int>>& edges, int N) {
        // Convert tuple format to times array
        vector<vector<int>> times;
        for (auto& [a, b, t] : edges) {
            times.push_back({a, b, t});
        }
        
        // Call original method with k = 0
        return networkDelayTime(times, N + 1, 0);
    }
    
    // Original method remains unchanged
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // [Original implementation from above]
        vector<vector<pair<int,int>>> g(n);
        for (auto& t : times) g[t[0]].emplace_back(t[1], t[2]);
        vector<bool> vis(n, false);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.emplace(0, k);
        int ans = 0, cnt = 0;
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = true; ans = d; cnt++;
            for (auto& [v, w] : g[u]) if (!vis[v]) pq.emplace(d+w, v);
        }
        return cnt == n ? ans : -1;
    }
};

Java

class Solution {
    public int messageDelayTime(int[][] edges, int N) {
        // Convert to times format (already compatible)
        // Call original method with k = 0
        return networkDelayTime(edges, N + 1, 0);
    }
    
    // Original method remains unchanged
    public int networkDelayTime(int[][] times, int n, int k) {
        // [Original implementation from above]
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new HashMap<>());
        for (int[] time : times) graph.get(time[0]).put(time[1], time[2]);
        Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[]{0, k});
        boolean[] vis = new boolean[n];
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (vis[u]) continue;
            vis[u] = true; ans = d;
            for (var entry : graph.get(u).entrySet()) {
                int v = entry.getKey(), w = entry.getValue();
                if (!vis[v]) pq.add(new int[]{d + w, v});
            }
        }
        for (boolean v : vis) if (!v) return -1;
        return ans;
    }
}

Python

from typing import List, Tuple

class Solution:
    def message_delay_time(self, edges: List[Tuple[int, int, int]], N: int) -> int:
        # Convert tuple format to times array
        times = [[a, b, t] for a, b, t in edges]
        
        # Call original method with k = 0
        return self.networkDelayTime(times, N + 1, 0)
    
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # [Original implementation from above]
        import heapq
        from collections import defaultdict
        
        g = defaultdict(list)
        for u, v, w in times:
            g[u].append((v, w))
        
        pq = [(0, k)]
        vis = set()
        ans = 0
        
        while pq:
            d, u = heapq.heappop(pq)
            if u in vis:
                continue
            vis.add(u)
            ans = d
            for v, w in g[u]:
                if v not in vis:
                    heapq.heappush(pq, (d + w, v))
        
        return ans if len(vis) == n else -1