Fewest hops between two services

MediumAbout 25 minProblem 1 of 2 in Graphs: breadth-first searchDraft

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

  1. fewestHops(5, [[0, 1], [1, 2], [2, 3], [0, 3], [3, 4]], 0, 4)returns 20 → 3 → 4.
  2. fewestHops(4, [[0, 1], [2, 3]], 0, 3)returns -1
  3. fewestHops(3, [[0, 1]], 2, 2)returns 0

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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open