Generated by Codex with GPT-5

Difficulty: MEDIUM
Problem: Network Delay Time

Problem gist

The input describes a directed, weighted graph. Each edge u -> v has a travel time w, and a signal starts at node k. The task is to return how long it takes until every node receives the signal. If some node can never receive it, return -1.

The key detail is that each node receives the signal as soon as the fastest path from k reaches it. So the answer is not the sum of every edge and not the time to walk through every node. It is the largest shortest-path distance from k to any node.

How to derive the solution

This problem becomes much easier once it is translated into shortest-path language:

• Nodes are computers.
• Directed edges are possible signal routes.
• Edge weights are route delays.
• The earliest arrival time at a node is the shortest distance from k.

Because every delay is non-negative, Dijkstra’s algorithm is the natural fit. Start with distance 0 at k and infinity everywhere else. Always expand the currently known node with the smallest arrival time. When an outgoing edge gives a neighbor a better arrival time, update that neighbor and put the improved time into a min-heap.

The min-heap matters because it lets the algorithm process nodes in the order they can be reached. Once the smallest pending time is popped, there is no undiscovered path that can reach that node earlier, because all edge weights only add time. That is the core correctness idea.

After Dijkstra finishes, scan the shortest arrival times. If any node is still infinity, it was unreachable. Otherwise, the answer is the maximum finite arrival time, because the whole network is done only when the slowest reachable node receives the signal.

Python solution

from heapq import heappop, heappush
from math import inf
from typing import List, Tuple


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = self._build_graph(times, n)
        shortest_arrival_times = self._dijkstra(graph, n, k)

        slowest_arrival_time = max(shortest_arrival_times[1:])
        return -1 if slowest_arrival_time == inf else slowest_arrival_time

    def _build_graph(
        self,
        times: List[List[int]],
        node_count: int,
    ) -> List[List[Tuple[int, int]]]:
        graph: List[List[Tuple[int, int]]] = [[] for _ in range(node_count + 1)]

        for source, target, travel_time in times:
            graph[source].append((target, travel_time))

        return graph

    def _dijkstra(
        self,
        graph: List[List[Tuple[int, int]]],
        node_count: int,
        start_node: int,
    ) -> List[float]:
        shortest_arrival_times = [inf] * (node_count + 1)
        shortest_arrival_times[start_node] = 0

        pending_nodes: List[Tuple[int, int]] = [(0, start_node)]

        while pending_nodes:
            current_time, current_node = heappop(pending_nodes)

            # Ignore heap entries that were made stale by a later, better path.
            if current_time > shortest_arrival_times[current_node]:
                continue

            for neighbor, travel_time in graph[current_node]:
                candidate_time = current_time + travel_time
                if candidate_time < shortest_arrival_times[neighbor]:
                    shortest_arrival_times[neighbor] = candidate_time
                    heappush(pending_nodes, (candidate_time, neighbor))

        return shortest_arrival_times

The time complexity is O((n + e) log n), where e is the number of directed edges in times. Building the graph is linear, and each useful distance improvement pushes an entry into the heap. The space complexity is O(n + e) for the adjacency list, distance array, and heap.

Interview follow-ups

What if the graph has negative edge weights?

Dijkstra’s algorithm depends on the fact that taking another edge never makes a path cheaper. Negative weights break that guarantee: a node that looked finalized could later become cheaper through a negative edge.

The expected replacement is Bellman-Ford. It relaxes every edge up to n - 1 times, which is enough because any shortest path without a negative cycle uses at most n - 1 edges. If a further relaxation is still possible after that, the graph contains a reachable negative cycle. The tradeoff is speed: Bellman-Ford takes O(n * e) time, which is much slower than Dijkstra on large sparse graphs, but it handles negative weights correctly.

What if the interviewer asks for the actual fastest paths, not just the time?

Keep a parent array while running Dijkstra. Whenever a node’s distance improves through current_node, set parent[neighbor] = current_node. After the algorithm finishes, reconstruct the path to any reachable target by walking backward through parent until reaching k, then reverse that list.

This does not change the asymptotic running time. It adds O(n) space for the parent array and O(path length) time to reconstruct one path. If every path must be printed, the output itself can take much more space.

What if there are multiple starting nodes sending the signal at the same time?

Use multi-source Dijkstra. Initialize the heap with (0, source) for every starting node, and set each source distance to 0. The rest of the algorithm is unchanged.

This works because adding several starting nodes is equivalent to adding a fake super-source with zero-cost edges to each real source. The complexity stays O((n + e) log n), with only a small increase from the initial heap entries.

What if the graph is dense or the interviewer asks for every starting node?

For one start node, heap-based Dijkstra is still usually practical. If the graph is dense and represented as a matrix, an O(n^2) Dijkstra variant can be competitive because almost every node connects to almost every other node.

If shortest paths are needed from every possible start node, the choice depends on constraints. Running Dijkstra from every node costs O(n * (n + e) log n), which is good for sparse graphs with non-negative weights. Floyd-Warshall costs O(n^3) time and O(n^2) space, but it is simple and can be better when the graph is dense or already stored as an adjacency matrix.

What if the graph is unweighted?

If every edge has the same delay, replace Dijkstra with breadth-first search. BFS visits nodes in increasing number of edges from the source, so the first visit gives the shortest arrival time in edge-count units.

This improves the running time to O(n + e) because no heap is needed. If every edge has the same non-one weight, BFS still works for reachability levels and the final distance is the number of edges multiplied by that common weight.