Fewest hops between two services
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
Services are numbered 0 to n - 1. Each entry of links is a pair [a, b]: the two services can call each other directly.
Return the fewest calls needed for a request to travel from service from to service to, or -1 if it cannot get there. From a service to itself takes 0 calls.
- 1 ≤ n ≤ 200,000
- 0 ≤ links.length ≤ 200,000
- links may repeat, and may join a service to itself
Examples
fewestHops(5, [[0, 1], [1, 2], [2, 3], [0, 3], [3, 4]], 0, 4)returns20 → 3 → 4.fewestHops(4, [[0, 1], [2, 3]], 0, 3)returns-1fewestHops(3, [[0, 1]], 2, 2)returns0
Hints
Hint 1 of 2
Build a list of neighbours for every service first; the links on their own are slow to search.
Hint 2 of 2
Search breadth-first from from, recording each service's distance when you first queue it. The first time you reach to is the answer.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Fewest hops in an unweighted network is what breadth-first search computes. It visits every service one call away before any two calls away, so the first time it reaches a service, it has found the shortest way there.
Build the neighbour lists first, in both directions, since a link works both ways. Mark a service with its distance when you add it to the queue. Marking only when you take it out lets the same service be queued once per link into it.
Depth-first search also visits everything, but in the order of whichever branch it tries first, so the first path it finds can be long. On 0 → 1 → 2 → 3 → 4 with a shortcut 0 → 3, it may walk the long way.
function fewestHops(n, links, from, to) {
if (from === to) return 0;
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of links) { adj[a].push(b); adj[b].push(a); }
const dist = new Int32Array(n).fill(-1);
dist[from] = 0;
const queue = [from];
for (let head = 0; head < queue.length; head++) {
const s = queue[head];
for (const t of adj[s]) {
if (dist[t] !== -1) continue;
dist[t] = dist[s] + 1;
if (t === to) return dist[t];
queue.push(t);
}
}
return -1;
}Complexity. O(n + m) time and space for n services and m links.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.