Watch 10 video solutions for Minimum Fuel Cost to Report to the Capital, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by NeetCodeIO has 15,393 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.
There is a meeting for the representatives of each city. The meeting is in the capital city.
There is a car in each city. You are given an integer seats that indicates the number of seats in each car.
A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.
Return the minimum number of liters of fuel to reach the capital city.
Example 1:
Input: roads = [[0,1],[0,2],[0,3]], seats = 5 Output: 3 Explanation: - Representative1 goes directly to the capital with 1 liter of fuel. - Representative2 goes directly to the capital with 1 liter of fuel. - Representative3 goes directly to the capital with 1 liter of fuel. It costs 3 liters of fuel at minimum. It can be proven that 3 is the minimum number of liters of fuel needed.
Example 2:
Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2 Output: 7 Explanation: - Representative2 goes directly to city 3 with 1 liter of fuel. - Representative2 and representative3 go together to city 1 with 1 liter of fuel. - Representative2 and representative3 go together to the capital with 1 liter of fuel. - Representative1 goes directly to the capital with 1 liter of fuel. - Representative5 goes directly to the capital with 1 liter of fuel. - Representative6 goes directly to city 4 with 1 liter of fuel. - Representative4 and representative6 go together to the capital with 1 liter of fuel. It costs 7 liters of fuel at minimum. It can be proven that 7 is the minimum number of liters of fuel needed.
Example 3:
Input: roads = [], seats = 1 Output: 0 Explanation: No representatives need to travel to the capital city.
Constraints:
1 <= n <= 105roads.length == n - 1roads[i].length == 20 <= ai, bi < nai != biroads represents a valid tree.1 <= seats <= 105Problem Overview: You are given n cities connected by n-1 roads forming a tree. Each city has one representative who must travel to the capital (city 0). Cars have seats capacity and consume one unit of fuel per road traveled. Representatives can share cars along the way. The task is to compute the minimum total fuel required for everyone to reach the capital.
Approach 1: DFS to Aggregate Representatives (O(n) time, O(n) space)
Treat the road network as a tree rooted at the capital. Use Depth-First Search to traverse from the capital and compute how many representatives exist in each subtree. Every node contributes one representative. When returning from a child subtree, calculate the number of cars required to move those representatives to the parent using ceil(representatives / seats). Each of those cars consumes one unit of fuel for the edge to the parent. Summing this value across all edges gives the minimum fuel. The key insight is that representatives naturally merge while moving upward, so the optimal strategy is always to combine them as early as possible in the tree.
Approach 2: BFS with Leaf Processing (O(n) time, O(n) space)
Build an adjacency list and track the degree of each node in the graph. Start from leaf nodes (excluding the capital) and process them using a queue with Breadth-First Search. Each leaf sends its representatives to its parent, requiring ceil(count / seats) cars for that edge. After processing, add its representative count to the parent and reduce the parent’s degree. When the parent becomes a leaf, push it into the queue. This bottom-up pruning approach effectively collapses the tree while accumulating the required fuel cost.
Recommended for interviews: The DFS aggregation approach is the most common solution. It directly models the tree structure and makes the representative merging logic clear. BFS leaf-pruning reaches the same result but is slightly less intuitive. Showing the DFS version first demonstrates strong understanding of tree traversal and subtree aggregation, which interviewers typically expect for this problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Subtree Aggregation | O(n) | O(n) | Most intuitive for tree problems; directly aggregates representatives from children |
| BFS Leaf Pruning | O(n) | O(n) | Useful when processing trees bottom-up using queue and node degrees |