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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Network Delay Time and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →