{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Network Delay Time – Solution & Complexity

Interview solutions
/
Network Delay Time

Solution Walkthrough

  1. Step 1: Recognize the Pattern

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

  2. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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)Cheapest Flights Within K Stops solution (medium)Word Ladder solution (hard)01 Matrix solution (medium)Accounts Merge solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?