Watch 10 video solutions for Count All Possible Routes, a hard level problem involving Array, Dynamic Programming, Memoization. This walkthrough by codestorywithMIK has 5,012 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.
At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.
Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).
Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5 Output: 4 Explanation: The following are all possible routes, each uses 5 units of fuel: 1 -> 3 1 -> 2 -> 3 1 -> 4 -> 3 1 -> 4 -> 2 -> 3
Example 2:
Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6 Output: 5 Explanation: The following are all possible routes: 1 -> 0, used fuel = 1 1 -> 2 -> 0, used fuel = 5 1 -> 2 -> 1 -> 0, used fuel = 5 1 -> 0 -> 1 -> 0, used fuel = 3 1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5
Example 3:
Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3 Output: 0 Explanation: It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.
Constraints:
2 <= locations.length <= 1001 <= locations[i] <= 109locations are distinct.0 <= start, finish < locations.length1 <= fuel <= 200Problem Overview: You are given city locations on a line, a start city, a finish city, and a limited amount of fuel. Moving between cities costs fuel equal to the distance between them. Count how many different routes can reach the finish city without the fuel dropping below zero. Cities can be revisited multiple times.
Approach 1: Recursive Depth-First Search (Exponential Time)
This approach explores every possible path using recursion. From the current city, iterate through all other cities and move if the fuel cost abs(locations[i] - locations[j]) is affordable. Each recursive call represents traveling to another city with reduced fuel. Whenever the current city equals the finish city, increment the route count. Because cities can be revisited, the recursion generates many repeated states, leading to O(n^fuel) worst-case time with O(fuel) recursion stack space. This method helps understand the search space but quickly becomes too slow for large inputs.
Approach 2: Dynamic Programming with Memoization (O(n² * fuel))
The key observation: the state is fully defined by the current city and remaining fuel. If you reach the same city again with the same fuel, the number of routes from that state will always be the same. Use a memo table dp[city][fuel] to cache results. For each state, iterate through all other cities, compute the fuel cost, and recursively count routes if enough fuel remains. Add 1 whenever the current city equals the finish city. Memoization avoids recomputation and collapses the exponential search into O(n² * fuel) time with O(n * fuel) space. This technique is a classic combination of dynamic programming and memoization, where overlapping subproblems are cached during recursion.
The transition looks like: from city i, try traveling to city j. If fuel >= abs(locations[i] - locations[j]), add the result of dfs(j, fuel - cost). Store the result in the DP table so future calls reuse it instantly. The total route count is typically taken modulo 1e9+7 to avoid overflow.
Recommended for interviews: Dynamic Programming with memoization. Interviewers expect you to recognize overlapping subproblems and convert the brute-force DFS into a cached state search. Explaining the naive DFS first shows understanding of the problem space, while the DP optimization demonstrates strong problem-solving skills with arrays and state-based DP.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | Exponential (≈ O(n^fuel)) | O(fuel) | Understanding the raw search space or explaining brute-force reasoning in interviews |
| Dynamic Programming with Memoization | O(n² * fuel) | O(n * fuel) | Optimal solution for constraints where cities and fuel states repeat frequently |