Interview Notes Search

This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.

Graphs

Network Delay Time

medium

DESCRIPTION (inspired by Leetcode.com)

A distributed system has n servers labeled 1 to n. The servers communicate through directed connections, where each connection [from, to, latency] means server from can send a message to server to with the given latency (in milliseconds).

When server k broadcasts an alert, it propagates through the network along all available paths. Return the minimum time required for every server to receive the alert. If some servers are unreachable from k, return -1.

Example 1:

Input:

connections = [[1,2,3], [1,3,5], [2,3,1]]
n = 3
k = 1

Output:

4

Explanation: There are two paths to server 3: the direct path 1→3 takes 5ms, but the path 1→2→3 takes only 3+1=4ms. The last server to receive the alert determines the answer.

Example 2:

Input:

connections = [[1,2,2], [3,2,1]]
n = 3
k = 1

Output:

-1

Explanation: The edge [3,2,1] points from server 3 to server 2, not the other way around. Server 1 can reach server 2, but there's no path from server 1 to server 3.

Explanation

Understanding the Problem

Choosing the Right Algorithm

The observation

Handling Unreachable Servers

How Dijkstra Works

Solution

Why Not BFS?