743. Network Delay Time (Medium)

Problem

You are given a network of n nodes. times[i] = [uᵢ, vᵢ, wᵢ] means a signal from uᵢ to vᵢ takes wᵢ time. Return the minimum time for a signal sent from node k to reach all nodes, or -1 if impossible.

Example

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 → 2
times = [[1,2,1]], n = 2, k = 1 → 1
times = [[1,2,1]], n = 2, k = 2 → -1

LeetCode 743 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, Bellman-Ford

Relax every edge n - 1 times.

def network_delay_time(times, n, k):
    INF = float('inf')
    dist = [INF] * (n + 1)          # L1: O(V) init
    dist[k] = 0                     # L2: O(1)
    for _ in range(n - 1):          # L3: outer loop, V-1 rounds
        for u, v, w in times:       # L4: iterate all edges, O(E) per round
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w   # L5: O(1) relaxation
    m = max(dist[1:])               # L6: O(V)
    return -1 if m == INF else m    # L7: O(1)

function networkDelayTime(times: number[][], n: number, k: number): number {
    const INF = Infinity;
    const dist = new Array(n + 1).fill(INF);  // L1: O(V) init
    dist[k] = 0;                               // L2: O(1)
    for (let round = 0; round < n - 1; round++) {  // L3: outer loop, V-1 rounds
        for (const [u, v, w] of times) {       // L4: iterate all edges, O(E) per round
            if (dist[u] + w < dist[v])
                dist[v] = dist[u] + w;         // L5: O(1) relaxation
        }
    }
    const m = Math.max(...dist.slice(1));      // L6: O(V)
    return m === INF ? -1 : m;                 // L7: O(1)
}

func networkDelayTime(times [][]int, n int, k int) int {
    const INF = 1<<31 - 1
    dist := make([]int, n+1)          // L1: O(V) init
    for i := range dist { dist[i] = INF }
    dist[k] = 0                       // L2: O(1)
    for round := 0; round < n-1; round++ {  // L3: outer loop, V-1 rounds
        for _, t := range times {     // L4: iterate all edges, O(E) per round
            u, v, w := t[0], t[1], t[2]
            if dist[u] != INF && dist[u]+w < dist[v] {
                dist[v] = dist[u] + w // L5: O(1) relaxation
            }
        }
    }
    m := 0
    for _, d := range dist[1:] {      // L6: O(V)
        if d == INF { return -1 }
        if d > m { m = d }
    }
    return m                          // L7: O(1)
}

final class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        let infinity = Int.max / 4; var distance = Array(repeating: infinity, count: n + 1); distance[k] = 0
        if n > 1 { for _ in 0..<(n - 1) { var changed = false; for edge in times where distance[edge[0]] < infinity { let candidate = distance[edge[0]] + edge[2]; if candidate < distance[edge[1]] { distance[edge[1]] = candidate; changed = true } }; if !changed { break } } }
        let answer = distance[1...n].max()!; return answer == infinity ? -1 : answer
    }
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(times).

Line	Per-call cost	Times executed	Contribution
L1 (init dist)	$O(1)$	V+1	$O(V)$
L2 (set source)	$O(1)$	1	$O(1)$
L3 (outer loop)	$O(1)$	V-1	$O(V)$
L4 (edge scan)	$O(1)$	E × (V-1)	$O(V · E)$ ← dominates
L5 (relaxation)	$O(1)$	up to E per round	$O(V · E)$
L6 (max)	$O(V)$	1	$O(V)$

L4 drives the cost: we walk all E edges once per round, for V-1 rounds. No priority ordering, no early-exit. Works for negative edges (given none here), but wastes work when only a fraction of edges improve each round.

Complexity

Time: $O(V · E)$ , driven by L4 (the full edge scan repeated V-1 times).
Space: $O(V)$ .

Works; overkill for non-negative weights.

Approach 2: Floyd-Warshall

Compute all-pairs shortest paths, then take max(dist[k][v]).

def network_delay_time(times, n, k):
    INF = float('inf')
    dist = [[INF] * (n + 1) for _ in range(n + 1)]     # L1: O(V²) init
    for i in range(n + 1):                              # L2: O(V) diagonal
        dist[i][i] = 0
    for u, v, w in times:                               # L3: O(E) seed edges
        dist[u][v] = w
    for mid in range(1, n + 1):                         # L4: outer pivot loop, V iters
        for i in range(1, n + 1):                       # L5: row loop, V iters
            for j in range(1, n + 1):                   # L6: col loop, V iters
                if dist[i][mid] + dist[mid][j] < dist[i][j]:
                    dist[i][j] = dist[i][mid] + dist[mid][j]   # L7: O(1) relax
    m = max(dist[k][1:])                                # L8: O(V)
    return -1 if m == INF else m                        # L9: O(1)

function networkDelayTime(times: number[][], n: number, k: number): number {
    const INF = Infinity;
    const dist: number[][] = Array.from({ length: n + 1 }, (_, i) =>
        Array.from({ length: n + 1 }, (_, j) => (i === j ? 0 : INF))
    );                                                  // L1: O(V²) init
    for (const [u, v, w] of times) dist[u][v] = w;    // L3: O(E) seed edges
    for (let mid = 1; mid <= n; mid++)                 // L4: outer pivot loop, V iters
        for (let i = 1; i <= n; i++)                   // L5: row loop, V iters
            for (let j = 1; j <= n; j++)               // L6: col loop, V iters
                if (dist[i][mid] + dist[mid][j] < dist[i][j])
                    dist[i][j] = dist[i][mid] + dist[mid][j];  // L7: O(1) relax
    const m = Math.max(...dist[k].slice(1));           // L8: O(V)
    return m === INF ? -1 : m;                         // L9: O(1)
}

func networkDelayTime(times [][]int, n int, k int) int {
    const INF = 1<<31 - 1
    dist := make([][]int, n+1)                          // L1: O(V²) init
    for i := range dist {
        dist[i] = make([]int, n+1)
        for j := range dist[i] {
            if i == j { dist[i][j] = 0 } else { dist[i][j] = INF }
        }
    }
    for _, t := range times {                           // L3: O(E) seed edges
        u, v, w := t[0], t[1], t[2]
        if w < dist[u][v] { dist[u][v] = w }
    }
    for mid := 1; mid <= n; mid++ {                     // L4: outer pivot loop, V iters
        for i := 1; i <= n; i++ {                       // L5: row loop, V iters
            for j := 1; j <= n; j++ {                   // L6: col loop, V iters
                if dist[i][mid] != INF && dist[mid][j] != INF &&
                    dist[i][mid]+dist[mid][j] < dist[i][j] {
                    dist[i][j] = dist[i][mid] + dist[mid][j] // L7: O(1) relax
                }
            }
        }
    }
    m := 0
    for j := 1; j <= n; j++ {                          // L8: O(V)
        if dist[k][j] == INF { return -1 }
        if dist[k][j] > m { m = dist[k][j] }
    }
    return m                                            // L9: O(1)
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(times).

Line	Per-call cost	Times executed	Contribution
L1 (init matrix)	$O(1)$	V²	$O(V²)$
L2 (diagonal)	$O(1)$	V	$O(V)$
L3 (seed edges)	$O(1)$	E	$O(E)$
L4 (pivot loop)	$O(1)$	V	$O(V)$
L5 (row loop)	$O(1)$	V²	$O(V²)$
L6, L7 (col + relax)	$O(1)$	V³	$O(V³)$ ← dominates
L8 (max)	$O(V)$	1	$O(V)$

The triple nested loop (L4/L5/L6) is the signature of Floyd-Warshall. Every (i, j, mid) triple is visited exactly once. This gives us all-pairs shortest paths, but for single-source we only need the k-th row — all the other rows are wasted work.

Complexity

Time: $O(V³)$ , driven by L6/L7 (the triple nested relaxation loop).
Space: $O(V²)$ .

Single-source only needs V²; Floyd-Warshall is wasteful here.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        let infinity = Int.max / 4; var distance = Array(repeating: Array(repeating: infinity, count: n), count: n)
        for i in 0..<n { distance[i][i] = 0 }; for edge in times { distance[edge[0] - 1][edge[1] - 1] = min(distance[edge[0] - 1][edge[1] - 1], edge[2]) }
        for middle in 0..<n { for from in 0..<n where distance[from][middle] < infinity { for to in 0..<n where distance[middle][to] < infinity { distance[from][to] = min(distance[from][to], distance[from][middle] + distance[middle][to]) } } }
        let answer = distance[k - 1].max()!; return answer == infinity ? -1 : answer
    }
}

Approach 3: Dijkstra with a binary heap (optimal)

Min-heap of (dist, node). Always expand the closest unvisited node.

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)                       # L1: O(1) init
    for u, v, w in times:                          # L2: O(E) build adjacency
        graph[u].append((v, w))

    dist = {k: 0}                                  # L3: O(1) seed source
    heap = [(0, k)]                                # L4: O(1) seed heap
    while heap:                                    # L5: loop until heap empty
        d, u = heapq.heappop(heap)                 # L6: O(log V) pop min
        if d > dist.get(u, float('inf')):          # L7: O(1) stale check
            continue
        for v, w in graph[u]:                      # L8: O(deg(u)) neighbor scan
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd                       # L9: O(1) update dist
                heapq.heappush(heap, (nd, v))      # L10: O(log V) push

    if len(dist) != n:                             # L11: O(1) reachability check
        return -1
    return max(dist.values())                      # L12: O(V)

function networkDelayTime(times: number[][], n: number, k: number): number {
    const graph = new Map<number, [number, number][]>();
    for (const [u, v, w] of times) {              // L2: O(E) build adjacency
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push([v, w]);
    }

    const dist = new Map<number, number>();
    dist.set(k, 0);                                // L3: O(1) seed source
    const heap = new MinHeap();
    heap.push([0, k]);                             // L4: O(1) seed heap

    while (heap.size > 0) {                       // L5: loop until heap empty
        const [d, u] = heap.pop();                // L6: O(log V) pop min
        if (d > (dist.get(u) ?? Infinity)) continue;  // L7: O(1) stale check
        for (const [v, w] of (graph.get(u) ?? [])) {  // L8: O(deg(u)) neighbor scan
            const nd = d + w;
            if (nd < (dist.get(v) ?? Infinity)) {
                dist.set(v, nd);                  // L9: O(1) update dist
                heap.push([nd, v]);               // L10: O(log V) push
            }
        }
    }

    if (dist.size !== n) return -1;              // L11: O(1) reachability check
    return Math.max(...dist.values());            // L12: O(V)
}

// See 743-network-delay-time-approach3.go for the full runnable program.
// Core function:
func networkDelayTime(times [][]int, n int, k int) int {
    graph := make(map[int][][2]int)
    for _, t := range times {                      // L2: O(E) build adjacency
        u, v, w := t[0], t[1], t[2]
        graph[u] = append(graph[u], [2]int{v, w})
    }
    dist := make(map[int]int)
    dist[k] = 0                                    // L3: O(1) seed source
    h := &MinHeap743{{node: k, dist: 0}}
    heap.Init(h)                                   // L4: O(1) seed heap
    for h.Len() > 0 {                              // L5: loop until heap empty
        item := heap.Pop(h).(Item743)
        d, u := item.dist, item.node               // L6: O(log V) pop min
        if best, ok := dist[u]; ok && d > best {   // L7: O(1) stale check
            continue
        }
        for _, edge := range graph[u] {            // L8: O(deg(u)) neighbor scan
            v, w := edge[0], edge[1]
            nd := d + w
            if best, ok := dist[v]; !ok || nd < best {
                dist[v] = nd                       // L9: O(1) update dist
                heap.Push(h, Item743{node: v, dist: nd})  // L10: O(log V) push
                heap.Fix(h, h.Len()-1)
            }
        }
    }
    if len(dist) != n { return -1 }               // L11: O(1) reachability check
    m := 0
    for _, v := range dist { if v > m { m = v } }
    return m                                       // L12: O(V)
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(times).

Line	Per-call cost	Times executed	Contribution
L1-L2 (build graph)	$O(1)$	E	$O(E)$
L3-L4 (seed)	$O(1)$	1	$O(1)$
L5 (loop test)	$O(1)$	up to E+1	$O(E)$
L6 (heappop)	$O(log V)$	up to E	$O(E log V)$ ← dominates
L7 (stale check)	$O(1)$	up to E	$O(E)$
L8 (neighbor scan)	$O(1)$	E total	$O(E)$
L10 (heappush)	$O(log V)$	up to E	$O(E log V)$ ← dominates
L12 (max)	$O(V)$	1	$O(V)$

Each edge can produce at most one push (L10), so the heap holds at most E entries. Each pop and push costs $O(log(heap size)$ ) = $O(log E)$ = $O(log V)$ since E ≤ V². The loop runs at most E times total (once per edge in the worst case). Combining: $O(E log V)$ for the heap work, plus $O(E)$ for the edge scanning, gives $O((V + E)$ log V) overall.

Complexity

Time: $O((V + E)$ log V), driven by L6/L10 (heap pop/push inside the main loop).
Space: $O(V + E)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        var graph = Array(repeating: [(Int, Int)](), count: n + 1); for edge in times { graph[edge[0]].append((edge[1], edge[2])) }
        let infinity = Int.max / 4; var distance = Array(repeating: infinity, count: n + 1); distance[k] = 0
        var queue = BinaryHeap<(Int, Int)>(hasHigherPriority: { $0.0 < $1.0 }); queue.insert((0, k))
        while let (elapsed, node) = queue.removeRoot() { if elapsed != distance[node] { continue }; for (neighbor, weight) in graph[node] { let candidate = elapsed + weight; if candidate < distance[neighbor] { distance[neighbor] = candidate; queue.insert((candidate, neighbor)) } } }
        let answer = distance[1...n].max()!; return answer == infinity ? -1 : answer
    }
}

Summary

Approach	Time	Space	When to use
Bellman-Ford	$O(V · E)$	$O(V)$	When negative edges are possible
Floyd-Warshall	$O(V³)$	$O(V²)$	All-pairs shortest paths
Dijkstra	$O((V + E)$ log V)	$O(V + E)$	Non-negative edges, single source

Dijkstra is the canonical SSSP for non-negative weights. Memorize the heap-based template.

Test cases

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = {k: 0}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    if len(dist) != n:
        return -1
    return max(dist.values())

def _run_tests():
    # Example 1: chain 2->1, 2->3, 3->4; source=2; answer=2
    assert network_delay_time([[2,1,1],[2,3,1],[3,4,1]], 4, 2) == 2
    # Example 2: single edge 1->2; source=1; answer=1
    assert network_delay_time([[1,2,1]], 2, 1) == 1
    # Example 3: single edge 1->2 but source=2; unreachable; answer=-1
    assert network_delay_time([[1,2,1]], 2, 2) == -1
    # Single node, no edges; trivially reached
    assert network_delay_time([], 1, 1) == 0
    # Two parallel paths, pick shortest
    assert network_delay_time([[1,2,1],[1,2,5]], 2, 1) == 1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses Dijkstra (Approach 3) with inline MinHeap.
class MinHeap {
    private data: [number, number][] = [];
    push(item: [number, number]): void {
        this.data.push(item);
        let i = this.data.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p][0] <= this.data[i][0]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
            i = p;
        }
    }
    pop(): [number, number] {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < this.data.length && this.data[l][0] < this.data[s][0]) s = l;
                if (r < this.data.length && this.data[r][0] < this.data[s][0]) s = r;
                if (s === i) break;
                [this.data[s], this.data[i]] = [this.data[i], this.data[s]];
                i = s;
            }
        }
        return top;
    }
    get size(): number { return this.data.length; }
}

function networkDelayTime(times: number[][], n: number, k: number): number {
    const graph = new Map<number, [number, number][]>();
    for (const [u, v, w] of times) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push([v, w]);
    }
    const dist = new Map<number, number>();
    dist.set(k, 0);
    const heap = new MinHeap();
    heap.push([0, k]);
    while (heap.size > 0) {
        const [d, u] = heap.pop();
        if (d > (dist.get(u) ?? Infinity)) continue;
        for (const [v, w] of (graph.get(u) ?? [])) {
            const nd = d + w;
            if (nd < (dist.get(v) ?? Infinity)) {
                dist.set(v, nd);
                heap.push([nd, v]);
            }
        }
    }
    if (dist.size !== n) return -1;
    return Math.max(...dist.values());
}

console.assert(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2) === 2);
console.assert(networkDelayTime([[1,2,1]], 2, 1) === 1);
console.assert(networkDelayTime([[1,2,1]], 2, 2) === -1);
console.assert(networkDelayTime([], 1, 1) === 0);
console.assert(networkDelayTime([[1,2,1],[1,2,5]], 2, 1) === 1);
console.log("all tests pass");

Graphs, shortest paths
Heaps / Priority Queues, Dijkstra frontier

Bellman-Ford, repeated-relaxation tactics for shortest paths with negative edges, bounded stops, or layered constraints.
Dijkstra, non-negative weighted shortest-path tactics using a priority queue frontier.
Shortest Paths, path-cost tactics for finding minimum distance, time, risk, or transformation count through a graph.

743. Network Delay Time (Medium)

Problem

Try it yourself

Approach 1: Brute force, Bellman-Ford

Approach 2: Floyd-Warshall

Approach 3: Dijkstra with a binary heap (optimal)

Summary

Test cases

Related data structures

Related concepts