Network Delay Time

HardGraphsdijkstra

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a directed, weighted network of n nodes labeled from 1 to n. A signal is broadcast from a single source node and propagates along the network's directed edges. The connections are described by a list times, where each entry times[i] = [u, v, w] means a signal sent from node u reaches node v after exactly w units of time travelling along that directed edge. A signal may fan out: when it arrives at a node, it is simultaneously forwarded along every outgoing edge of that node. Given times, the number of nodes n, and the label k of the source node, return the minimum amount of time required for the signal to reach **every** node in the network. If it is impossible for all n nodes to receive the signal, return -1. The time for a single node to be reached is the length of the shortest path from k to that node. The answer is the largest of these shortest-path times over all nodes, since the whole network is "covered" only once the slowest-reached node has gotten the signal.

Examples

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Starting at node 2: node 1 is reached at time 1, node 3 at time 1, and node 4 at time 1+1=2. The slowest arrival is 2, so the network is fully covered at time 2.
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
From node 1 the signal reaches node 2 in 1 unit. Both nodes are covered, and the maximum arrival time is 1.
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Starting at node 2, there is no outgoing edge, so node 1 can never be reached. Not all nodes receive the signal, so the answer is -1.

Constraints

  • `1 <= k <= n <= 100`
  • `0 <= times.length <= n * (n - 1)`
  • `times[i].length == 3`
  • `1 <= u, v <= n`
  • `u != v` (no self-loops)
  • `1 <= w <= 100`
  • All `(u, v)` pairs are unique (no duplicate directed edges)

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dijkstra problems