Scale Engineer

Count All Possible Routes

Hard
#1449Time: O(n^fuel), where n is the number of locations. In the worst case, from each city, we can branch to `n-1` other cities. The recursion depth can be up to `fuel` (since the minimum fuel cost is 1 for distinct locations), leading to an exponential number of calls.Space: O(fuel). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to the initial fuel.
Patterns
Dynamic ProgrammingMemoization
Data structures
Array

Prompt

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 <= 100
  • 1 <= locations[i] <= 109
  • All integers in locations are distinct.
  • 0 <= start, finish < locations.length
  • 1 <= fuel <= 200

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem into a recursive function. We define a function solve(currentCity, remainingFuel) that explores all possible next moves from currentCity. For each valid move to a city j, it makes a recursive call with the updated fuel. The base case is when we are at the finish city, which counts as one valid route.

Algorithm

  1. Define a recursive function solve(currentCity, remainingFuel).
  2. Initialize a counter count to 0. If currentCity is the finish city, set count to 1 to account for the route ending at the destination.
  3. Iterate through all possible next cities j from 0 to n-1.
  4. If j is the same as currentCity, skip to the next city.
  5. Calculate the fuel cost required to travel from currentCity to j: cost = |locations[currentCity] - locations[j]|.
  6. If remainingFuel is sufficient for the travel (i.e., remainingFuel >= cost):
    • Make a recursive call solve(j, remainingFuel - cost) to find the number of routes from city j.
    • Add the result of the recursive call to count.
    • Apply modulo 10^9 + 7 to count to prevent overflow.
  7. Return the total count.
  8. The main function initiates the process by calling solve(start, fuel).

Walkthrough

We define a recursive helper function, say solve(curr, fuelLeft), that calculates the number of ways to reach the finish city starting from curr with fuelLeft amount of fuel. If fuelLeft becomes negative, it signifies an invalid path, and the function returns 0. We initialize a variable ans. If curr is the finish city, we set ans to 1, as this represents a valid route that ends at this point. Then, we iterate through all possible next cities nextCity. For each nextCity that is different from curr, we calculate the fuelNeeded. If fuelLeft >= fuelNeeded, we can make this move. We then recursively call solve(nextCity, fuelLeft - fuelNeeded) and add the returned value to ans. To handle potentially large results, all additions are performed modulo 10^9 + 7. The process starts with an initial call to solve(start, fuel). This method is very slow because it repeatedly recomputes the results for the same state (curr, fuelLeft), leading to an exponential time complexity.

class Solution {    int finish;    int[] locations;    int MOD = 1_000_000_007;     public int countRoutes(int[] locations, int start, int finish, int fuel) {        this.locations = locations;        this.finish = finish;        return solve(start, fuel);    }     private int solve(int currentCity, int remainingFuel) {        if (remainingFuel < 0) {            return 0;        }         long ans = 0;        if (currentCity == finish) {            ans = 1;        }         for (int nextCity = 0; nextCity < locations.length; nextCity++) {            if (nextCity == currentCity) {                continue;            }            int cost = Math.abs(locations[currentCity] - locations[nextCity]);            if (remainingFuel >= cost) {                ans = (ans + solve(nextCity, remainingFuel - cost)) % MOD;            }        }         return (int) ans;    }}

Complexity

Time

O(n^fuel), where n is the number of locations. In the worst case, from each city, we can branch to `n-1` other cities. The recursion depth can be up to `fuel` (since the minimum fuel cost is 1 for distinct locations), leading to an exponential number of calls.

Space

O(fuel). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to the initial fuel.

Trade-offs

Pros

  • Simple to understand and implement as it directly models the problem's state transitions.

  • Requires minimal data structures.

Cons

  • Extremely inefficient due to an exponential number of redundant calculations.

  • Will result in a 'Time Limit Exceeded' error for all but the smallest inputs.

Solutions

class Solution {private  int[] locations;private  int finish;private  int n;private  Integer[][] f;private  final int mod = (int)1 e9 + 7;public  int countRoutes(int[] locations, int start, int finish, int fuel) {    n = locations.length;    this.locations = locations;    this.finish = finish;    f = new Integer[n][fuel + 1];    return dfs(start, fuel);  }private  int dfs(int i, int k) {    if (k < Math.abs(locations[i] - locations[finish])) {      return 0;    }    if (f[i][k] != null) {      return f[i][k];    }    int ans = i == finish ? 1 : 0;    for (int j = 0; j < n; ++j) {      if (j != i) {        ans = (ans + dfs(j, k - Math.abs(locations[i] - locations[j]))) % mod;      }    }    return f[i][k] = ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem