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 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.
Input: times =[[2,1,1],[2,3,1],[3,4,1]], n =4, k =2Output: 2
Example 2:
1
2
Input: times =[[1,2,1]], n =2, k =1Output: 1
Example 3:
1
2
Input: times =[[1,2,1]], n =2, k =2Output: -1
Variant 1 - Message Propagation Time (Daily Coding Problem 270)#
This variant represents the same core problem with a slightly different presentation, corresponding to Daily Coding Problem 270 asked by Twitter.
A network consists of nodes labeled 0 to N. You are given a list of edges (a, b, t), describing the time t it takes for a message to be sent from node a to node b. Whenever a node receives a message, it immediately passes the message on to a neighboring node, if possible.
Assuming all nodes are connected, determine how long it will take for every node to receive a message that begins at node 0.
We need to find the shortest path from a given node to all other nodes. This is a classic shortest path problem that can be solved using Dijkstra’s algorithm. The key insight is that we want to find the maximum time among all shortest paths, as this represents when the last node receives the signal.
classSolution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int,int>>> g(n+1);
for (auto& t : times) g[t[0]].emplace_back(t[1], t[2]);
vector<bool> vis(n+1, false);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, k);
int ans =0, cnt =0;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u] = true; ans = d; cnt++;
for (auto& [v, w] : g[u]) if (!vis[v]) pq.emplace(d+w, v);
}
return cnt == n ? ans : -1;
}
};
classSolution {
publicintnetworkDelayTime(int[][] times, int n, int k) {
Map<Integer, Map<Integer, Integer>> graph =new HashMap<>();
for (int i = 1; i <= n; i++) graph.put(i, new HashMap<>());
for (int[] time : times) graph.get(time[0]).put(time[1], time[2]);
Queue<int[]> pq =new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(newint[]{0, k});
boolean[] vis =newboolean[n + 1];
int ans = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (vis[u]) continue;
vis[u]=true; ans = d;
for (var entry : graph.get(u).entrySet()) {
int v = entry.getKey(), w = entry.getValue();
if (!vis[v]) pq.add(newint[]{d + w, v});
}
}
for (int i = 1; i <= n; i++) if (!vis[i]) return-1;
return ans;
}
}
import heapq
from collections import defaultdict
classSolution:
defnetworkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g = defaultdict(list)
for u, v, w in times:
g[u].append((v, w))
vis = set()
pq = [(0, k)]
ans =0while pq:
d, u = heapq.heappop(pq)
if u in vis:
continue vis.add(u)
ans = d
for v, w in g[u]:
if v notin vis:
heapq.heappush(pq, (d + w, v))
return ans if len(vis) == n else-1
⏰ Time complexity: O(E log N) where E is the number of edges and N is the number of nodes (for Dijkstra’s algorithm).
🧺 Space complexity: O(N + E) for the graph and visited structures.
Solution for Variant 1 - Message Propagation Time#
Since this is essentially the same problem with different input format and starting node, we can reuse the original networkDelayTime solution by simply converting the input format and setting k = 0.
classSolution {
public:int messageDelayTime(vector<tuple<int,int,int>>& edges, int N) {
// Convert tuple format to times array
vector<vector<int>> times;
for (auto& [a, b, t] : edges) {
times.push_back({a, b, t});
}
// Call original method with k = 0
returnnetworkDelayTime(times, N +1, 0);
}
// Original method remains unchanged
intnetworkDelayTime(vector<vector<int>>& times, int n, int k) {
// [Original implementation from above]
vector<vector<pair<int,int>>> g(n);
for (auto& t : times) g[t[0]].emplace_back(t[1], t[2]);
vector<bool> vis(n, false);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.emplace(0, k);
int ans =0, cnt =0;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u] = true; ans = d; cnt++;
for (auto& [v, w] : g[u]) if (!vis[v]) pq.emplace(d+w, v);
}
return cnt == n ? ans : -1;
}
};
classSolution {
publicintmessageDelayTime(int[][] edges, int N) {
// Convert to times format (already compatible)// Call original method with k = 0return networkDelayTime(edges, N + 1, 0);
}
// Original method remains unchangedpublicintnetworkDelayTime(int[][] times, int n, int k) {
// [Original implementation from above] Map<Integer, Map<Integer, Integer>> graph =new HashMap<>();
for (int i = 0; i < n; i++) graph.put(i, new HashMap<>());
for (int[] time : times) graph.get(time[0]).put(time[1], time[2]);
Queue<int[]> pq =new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(newint[]{0, k});
boolean[] vis =newboolean[n];
int ans = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (vis[u]) continue;
vis[u]=true; ans = d;
for (var entry : graph.get(u).entrySet()) {
int v = entry.getKey(), w = entry.getValue();
if (!vis[v]) pq.add(newint[]{d + w, v});
}
}
for (boolean v : vis) if (!v) return-1;
return ans;
}
}
from typing import List, Tuple
classSolution:
defmessage_delay_time(self, edges: List[Tuple[int, int, int]], N: int) -> int:
# Convert tuple format to times array times = [[a, b, t] for a, b, t in edges]
# Call original method with k = 0return self.networkDelayTime(times, N +1, 0)
defnetworkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# [Original implementation from above]import heapq
from collections import defaultdict
g = defaultdict(list)
for u, v, w in times:
g[u].append((v, w))
pq = [(0, k)]
vis = set()
ans =0while pq:
d, u = heapq.heappop(pq)
if u in vis:
continue vis.add(u)
ans = d
for v, w in g[u]:
if v notin vis:
heapq.heappush(pq, (d + w, v))
return ans if len(vis) == n else-1
⏰ Time complexity: O(E log N) - Same as main problem
🧺 Space complexity: O(N + E) - Same as main problem
This elegant solution demonstrates how problem variants can often be solved by simple input/output transformations rather than rewriting the entire algorithm.