Bakery Chute Transfer Map
Fewest edges from a start node to every node in a directed graph
A bakery has n workstations numbered from 0 to n - 1. Trays can travel between workstations through one-way chutes.
Each entry [a, b] in chutes means a tray can move directly from workstation a to workstation b. This does not allow travel in the reverse direction unless that chute is listed separately. Passing through any one chute counts as one transfer.
A tray begins at workstation start. Return a list of length n whose entry at index i is the minimum number of transfers needed to reach workstation i. Use -1 if that workstation cannot be reached.
The entry for start must be 0. Chutes may form cycles, connect a workstation to itself, or appear more than once.
Examples
Example 1
Input: n = 5, chutes = [[0,1],[1,2],[0,3],[3,2],[2,4]], start = 0 Output: [0,1,2,1,3]
From workstation 0, workstations 1 and 3 each need one transfer. Workstation 2 needs two transfers, and workstation 4 needs three.
Example 2
Input: n = 4, chutes = [[0,1],[2,1]], start = 2 Output: [-1,1,0,-1]
The tray starts at workstation 2 and can reach workstation 1 directly. The chute from 0 to 1 cannot be used backward, so workstation 0 remains unreachable. Workstation 3 is also unreachable.
Example 3
Input: n = 1, chutes = [], start = 0 Output: [0]
The tray is already at the only workstation, so no transfer is needed.
Constraints
- 1 <= n <= 2000
- 0 <= chutes.length <= 3000
- Each entry in chutes contains exactly two integers.
- 0 <= a, b < n for every chute [a, b]
- 0 <= start < n
Return entries in workstation-number order, not traversal order. The intended solution runs in O(n + chutes.length) time and uses O(n + chutes.length) space.
Hints
Show hint 1Hint 1
Explore the workstations in layers: first those reachable in one transfer, then those reachable in two transfers, and so on.
Show hint 2Hint 2
Use a queue and assign a workstation's distance when it is first discovered.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return one shortest route to a specified destination?
- How would the approach change if each chute had its own positive transfer time?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem