{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Network Delay Time – Solution & Complexity

Interview solutions
/
Network Delay Time

1. Recognize the Pattern

The key pattern is: Dijkstra settles nodes by earliest signal arrival. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O((V + E) log V). Space: O(V + E).

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    import heapq
    graph = [[] for _ in range(n + 1)]
    for source, target, weight in times: graph[source].append((weight, target))
    heap, distance = [(0, k)], {}
    while heap:
        elapsed, node = heapq.heappop(heap)
        if node in distance: continue
        distance[node] = elapsed
        for weight, neighbor in graph[node]:
            if neighbor not in distance: heapq.heappush(heap, (elapsed + weight, neighbor))
    return max(distance.values()) if len(distance) == n else -1

FAQ

See also

Practice Network Delay Time online (run code in the browser)Clone Graph solution (medium)Course Schedule solution (medium)Find Median from Data Stream solution (hard)Kth Largest Element in an Array solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?