Skip to main content

743. Network Delay Time

medium

Send a signal from node k through a weighted directed network; return the time for it to reach every node, or -1 if unreachable. Textbook single-source shortest path — Dijkstra with a min-heap is the expected answer.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

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.

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

All-nodes-received time = max of the shortest distances from k. So compute shortest path from k to every node.

Hint 2

Non-negative weights -> Dijkstra. Priority queue keyed on (current distance, node).

Hint 3

After Dijkstra finishes, scan the distance array. If any node is still infinity, return -1. Otherwise return the max.

Solution approach

Reveal approach

Build an adjacency list grouping by source. Initialize a dist array with infinity, set dist[k] = 0. Push (0, k) onto a min-heap. Pop the smallest (d, u); if d > dist[u] skip (stale entry). For each (v, w) neighbor of u, if d + w < dist[v], update dist[v] = d + w and push (dist[v], v). After the heap drains, scan dist[1..n]: if any is infinity, return -1, else return max(dist). Standard Dijkstra runs in O((V + E) log V) with a binary heap. The 'skip stale' check is the easy-to-forget detail — without it, the heap can fill with outdated entries and slow you down.

Complexity

Time
O((V + E) log V)
Space
O(V + E)

Related patterns

  • dijkstra
  • shortest-path
  • heap
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Uber

More Graphs practice problems

See all Graphs problems →