Leetcode #1466: Reorder Routes to Make All Paths Lead to the City Zero
In this guide, we solve Leetcode #1466 Reorder Routes to Make All Paths Lead to the City Zero in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Depth-First Search, Breadth-First Search, Graph
Intuition
The data forms a graph, so we should explore nodes and edges systematically.
A traversal ensures we visit each node once while maintaining the needed state.
Approach
Build an adjacency list and traverse with BFS or DFS.
Aggregate results as you visit nodes.
Steps:
- Build the graph.
- Traverse with BFS/DFS.
- Accumulate the required output.
Example
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Python Solution
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
def dfs(a: int, fa: int) -> int:
return sum(c + dfs(b, a) for b, c in g[a] if b != fa)
g = [[] for _ in range(n)]
for a, b in connections:
g[a].append((b, 1))
g[b].append((a, 0))
return dfs(0, -1)
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.