743. Network Delay Time LeetCode Solution

Last updated: February 19, 2025

In this guide, you will get 743. Network Delay Time LeetCode Solution with the best time and space complexity. The solution to Network Delay Time problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Network Delay Time solution in C++
Network Delay Time solution in Java
Network Delay Time solution in Python
Additional Resources

743. Network Delay Time LeetCode Solution image

Problem Statement of Network Delay Time

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 time it takes for a signal to travel 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.

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 the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Complexity Analysis

Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|V| + |E|)

743. Network Delay Time LeetCode Solution in C++

class Solution {
 public:
  int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int, int>>> graph(n);

    for (const vector<int>& time : times) {
      const int u = time[0] - 1;
      const int v = time[1] - 1;
      const int w = time[2];
      graph[u].emplace_back(v, w);
    }

    return dijkstra(graph, k - 1);
  }

 private:
  int dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
    vector<int> dist(graph.size(), INT_MAX);

    dist[src] = 0;
    using P = pair<int, int>;  // (d, u)
    priority_queue<P, vector<P>, greater<>> minHeap;
    minHeap.emplace(dist[src], src);

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (d > dist[u])
        continue;
      for (const auto& [v, w] : graph[u])
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.emplace(dist[v], v);
        }
    }

    const int maxDist = ranges::max(dist);
    return maxDist == INT_MAX ? -1 : maxDist;
  }
};
/* code provided by PROGIEZ */

743. Network Delay Time LeetCode Solution in Java

class Solution {
  public int networkDelayTime(int[][] times, int n, int k) {
    List<Pair<Integer, Integer>>[] graph = new List[n];

    for (int i = 0; i < n; i++)
      graph[i] = new ArrayList<>();

    for (int[] time : times) {
      final int u = time[0] - 1;
      final int v = time[1] - 1;
      final int w = time[2];
      graph[u].add(new Pair<>(v, w));
    }

    return dijkstra(graph, k - 1);
  }

  private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src) {
    int[] dist = new int[graph.length];
    Arrays.fill(dist, Integer.MAX_VALUE);

    dist[src] = 0;
    Queue<Pair<Integer, Integer>> minHeap =
        new PriorityQueue<>(Comparator.comparing(Pair::getKey)) {
          { offer(new Pair<>(dist[src], src)); } // (d, u)
        };

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek().getKey();
      final int u = minHeap.poll().getValue();
      if (d > dist[u])
        continue;
      for (Pair<Integer, Integer> pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        if (d + w < dist[v]) {
          dist[v] = d + w;
          minHeap.offer(new Pair<>(dist[v], v));
        }
      }
    }

    final int maxDist = Arrays.stream(dist).max().getAsInt();
    return maxDist == Integer.MAX_VALUE ? -1 : maxDist;
  }
}
// code provided by PROGIEZ

743. Network Delay Time LeetCode Solution in Python

class Solution:
  def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
    graph = [[] for _ in range(n)]

    for u, v, w in times:
      graph[u - 1].append((v - 1, w))

    return self._dijkstra(graph, k - 1)

  def _dijkstra(self, graph: list[list[tuple[int, int]]], src: int) -> int:
    dist = [math.inf] * len(graph)

    dist[src] = 0
    minHeap = [(dist[src], src)]  # (d, u)

    while minHeap:
      d, u = heapq.heappop(minHeap)
      if d > dist[u]:
        continue
      for v, w in graph[u]:
        if d + w < dist[v]:
          dist[v] = d + w
          heapq.heappush(minHeap, (dist[v], v))

    maxDist = max(dist)
    return maxDist if maxDist != math.inf else -1
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents