Tech Blogs LLD SDE Playbook DSA

Network Delay Time

Medium Top 250
Associated Patterns
Graphs Heap & Priority Queue
Interviewed At (Company Tags)
GoogleAmazonMicrosoft
External Reference View on LeetCode

Problem Description

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = [ui, vi, wi], where ui is the source node, vi is the target node, and wi is the travel time from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Examples

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1 Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2 Output: -1

Constraints

  • 1 ≤ k ≤ n ≤ 100
  • 1 ≤ times.length ≤ 6000
  • times[i].length == 3
  • 1 ≤ ui, vi ≤ n
  • ui != vi
  • 0 ≤ wi ≤ 100
  • All pairs (ui, vi) are unique.

Standard Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path (minimum time) from a single source node k to all other nodes in a weighted graph.

  1. Build an adjacency list where each node points to list of [neighbor, weight] pairs.
  2. Initialize a distances array of size n + 1 with infinity, and distances[k] = 0.
  3. Use a min-heap to store [time, node] pairs, sorted by time. Seed it with [0, k].
  4. While the heap is not empty, pop the element [time, node] with the smallest time.
    • If time > distances[node], skip it.
    • For each neighbor [neighbor, weight] of node:
      • If time + weight < distances[neighbor], update distances[neighbor] = time + weight and push [time + weight, neighbor] to the heap.
  5. The answer is the maximum value in distances (skipping index 0 and index k). If any node is unreachable (distance remains infinity), return -1.

Solution: Dijkstra

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] t : times) {
            adj.get(t[0]).add(new int[]{t[1], t[2]}); // [neighbor, weight]
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        // min-heap: [distance, node]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[]{0, k});

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], node = top[1];

            if (d > dist[node]) continue;

            for (int[] edge : adj.get(node)) {
                int neighbor = edge[0], weight = edge[1];
                if (d + weight < dist[neighbor]) {
                    dist[neighbor] = d + weight;
                    heap.offer(new int[]{dist[neighbor], neighbor});
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1; // unreachable node
            maxTime = Math.max(maxTime, dist[i]);
        }

        return maxTime;
    }
}
import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))

        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0

        # min-heap: (distance, node)
        heap = [(0, k)]

        while heap:
            d, node = heapq.heappop(heap)

            if d > dist[node]:
                continue

            for neighbor, weight in adj[node]:
                if d + weight < dist[neighbor]:
                    dist[neighbor] = d + weight
                    heapq.heappush(heap, (d + weight, neighbor))

        max_time = max(dist.values())
        return max_time if max_time != float('inf') else -1
#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
        std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
        for (const auto& t : times) {
            adj[t[0]].push_back({t[1], t[2]});
        }

        std::vector<int> dist(n + 1, 1e9);
        dist[k] = 0;

        // min-heap: {distance, node}
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> heap;
        heap.push({0, k});

        while (!heap.empty()) {
            auto [d, node] = heap.top(); heap.pop();

            if (d > dist[node]) continue;

            for (const auto& edge : adj[node]) {
                int neighbor = edge.first, weight = edge.second;
                if (d + weight < dist[neighbor]) {
                    dist[neighbor] = d + weight;
                    heap.push({dist[neighbor], neighbor});
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == 1e9) return -1;
            maxTime = std::max(maxTime, dist[i]);
        }

        return maxTime;
    }
};

Complexity Analysis:

  • Time Complexity: O(E log V) = O(E log N) where E is the number of edges and N is the number of nodes.
  • Space Complexity: O(N + E) to store the adjacency list representation.

← All Problems