#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-ii-trees-graphs-dynamic-programming/lc-743-network-delay-time-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-ii-trees-graphs-dynamic-programming/lc-743-network-delay-time-implementation

Repovive

LeetCode 743 Network Delay Time - Implementation - Coding Patterns II: Trees, Graphs & Dynamic Programming | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 743 Network Delay Time - Implementation

The code

Build an adjacency list, run Dijkstra from node k, and return the max distance.

function networkDelayTime(times, n, k):
    graph = adjacency list from times
    dist = array of size n+1, filled with infinity
    dist[k] = 0
    heap = min-heap with (0, k)
    while heap is not empty:
        d, node = heap.pop()
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            newDist = d + weight
            if newDist < dist[neighbor]:
                dist[neighbor] = newDist
                heap.push((newDist, neighbor))
    maxDist = max(dist[1..n])
    if maxDist == infinity:
        return -1
    return maxDist

$O(E \log V)$ time, $O(V + E)$ space.