Scale Engineer

Network Delay Time

Med
#0697Time: O(n * E), where `n` is the number of nodes and `E` is the number of edges. The outer loop runs `n-1` times, and the inner loop iterates through all `E` edges.Space: O(n) to store the `dist` array.2 companies
Algorithms
Depth-First SearchBreadth-First SearchShortest Path
Data structures
Heap (Priority Queue)Graph
Companies
NetflixAkuna Capital

Prompt

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.)

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses the Bellman-Ford algorithm to find the shortest paths from the source node k to all other nodes. Bellman-Ford is capable of handling graphs with negative edge weights, although this problem has only non-negative weights. It works by iteratively relaxing edges, which involves repeatedly checking and updating shortest path estimates until they converge.

Algorithm

  • Initialize a distance array dist of size n+1 with a large value (infinity) to store the shortest travel times from k.
  • Set dist[k] = 0.
  • Repeat n-1 times:
    • For each edge (u, v) with weight w in times:
      • If dist[u] is not infinity and dist[u] + w < dist[v], update dist[v] = dist[u] + w.
  • After the loops, find the maximum value in the dist array (from dist[1] to dist[n]). Let this be max_dist.
  • If max_dist is infinity, it means at least one node is unreachable. Return -1.
  • Otherwise, return max_dist.

Walkthrough

The Bellman-Ford algorithm computes single-source shortest paths in a weighted directed graph. First, we initialize a distance array dist of size n+1 with infinity for all nodes, except for the source node k, which is set to 0. The algorithm then relaxes all edges (u, v) with weight w for n-1 times. A relaxation step checks if the path to v can be shortened by going through u. If dist[u] + w < dist[v], we update dist[v] to dist[u] + w. After n-1 iterations, the dist array will contain the shortest path distances from k to all other nodes, provided there are no negative-weight cycles (which is true here). Finally, we find the maximum distance in the dist array among all reachable nodes. If any distance is still infinity, it means that node is unreachable, and we should return -1. The result is the maximum finite distance found.

import java.util.Arrays; class Solution {    public int networkDelayTime(int[][] times, int n, int k) {        int[] dist = new int[n + 1];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[k] = 0;         for (int i = 0; i < n - 1; i++) {            boolean updated = false;            for (int[] edge : times) {                int u = edge[0];                int v = edge[1];                int w = edge[2];                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {                    dist[v] = dist[u] + w;                    updated = true;                }            }            // Optimization: if no distances were updated in an iteration, we can stop early.            if (!updated) {                break;            }        }         int maxWait = 0;        for (int i = 1; i <= n; i++) {            if (dist[i] == Integer.MAX_VALUE) {                return -1;            }            maxWait = Math.max(maxWait, dist[i]);        }         return maxWait;    }}

Complexity

Time

O(n * E), where `n` is the number of nodes and `E` is the number of edges. The outer loop runs `n-1` times, and the inner loop iterates through all `E` edges.

Space

O(n) to store the `dist` array.

Trade-offs

Pros

  • Relatively simple to implement.

  • Can handle negative edge weights (though not needed for this problem).

Cons

  • Less efficient than Dijkstra's algorithm for graphs with non-negative weights.

  • For the given constraints, it's the slowest approach.

Solutions

class Solution {private  static final int N = 110;private  static final int INF = 0x3f3f;public  int networkDelayTime(int[][] times, int n, int k) {    int[][] g = new int[N][N];    for (int i = 0; i < N; ++i) {      Arrays.fill(g[i], INF);    }    for (int[] e : times) {      g[e[0]][e[1]] = e[2];    }    int[] dist = new int[N];    Arrays.fill(dist, INF);    dist[k] = 0;    boolean[] vis = new boolean[N];    for (int i = 0; i < n; ++i) {      int t = -1;      for (int j = 1; j <= n; ++j) {        if (!vis[j] && (t == -1 || dist[t] > dist[j])) {          t = j;        }      }      vis[t] = true;      for (int j = 1; j <= n; ++j) {        dist[j] = Math.min(dist[j], dist[t] + g[t][j]);      }    }    int ans = 0;    for (int i = 1; i <= n; ++i) {      ans = Math.max(ans, dist[i]);    }    return ans == INF ? -1 : ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem