Problem Description

You have an array locations containing distinct positive integers, where locations[i] represents the position of city i. You're given three additional parameters:

• start: the index of your starting city
• finish: the index of your destination city
• fuel: the initial amount of fuel you have

Movement Rules:

• From any city i, you can move to any other city j (where j ≠ i)
• Moving from city i to city j costs |locations[i] - locations[j]| fuel (the absolute difference between their positions)
• You cannot make a move if it would cause your fuel to become negative
• You can visit any city multiple times, including the start and finish cities

Goal: Count all possible routes from the start city to the finish city without running out of fuel.

Important Notes:

• A route is considered valid as long as it ends at the finish city with non-negative fuel remaining
• You get credit for reaching the finish city each time you arrive there - if you're already at the finish city, that counts as one valid route, and you can continue traveling to accumulate more routes
• Return the total count modulo 10^9 + 7 since the answer might be very large

Example Understanding: If you start at city start and it happens to be the same as finish, that immediately counts as one valid route. You can then travel to other cities and return to finish again, with each arrival counting as another valid route, as long as you have sufficient fuel for each journey.

Intuition

The key insight is that this is a path counting problem where we need to explore all possible routes. Since we can revisit cities multiple times, we might end up calculating the same subproblem repeatedly - for instance, arriving at the same city with the same amount of fuel through different routes.

Think about it this way: if we're at city i with k fuel remaining, the number of valid routes from this state to the finish doesn't depend on how we got to city i - it only depends on our current position and remaining fuel. This observation suggests using dynamic programming with memoization.

We can break down the problem recursively:

• From any city i with k fuel, we need to count all possible ways to reach the finish
• We can try moving to every other city j, which costs |locations[i] - locations[j]| fuel
• For each valid move (where we have enough fuel), we recursively count the routes from the new position

The base cases emerge naturally:

1. If we're at the finish city, we've found one valid route (but we can continue traveling to find more)
2. If we don't have enough fuel to reach the finish city even by the shortest possible path (k < |locations[i] - locations[finish]|), then there are no valid routes from this state

The beauty of this approach is that by using memoization with @cache, we avoid recalculating the number of routes from the same (city, fuel) state multiple times. Each unique state is computed only once, making the solution efficient despite the potentially large number of possible paths.

The recursive function dfs(i, k) naturally captures this idea: "How many ways can I reach the finish from city i with k fuel?" The answer accumulates by trying all possible next moves and summing up their route counts.

Learn more about Memoization and Dynamic Programming patterns.

Solution Approach

The solution uses memoization with depth-first search (DFS) to count all possible routes efficiently.

Core Function Design:

We define dfs(i, k) to represent the number of valid routes from city i to the finish city with k units of fuel remaining. The answer to our problem is simply dfs(start, fuel).

Implementation Steps:

1. Early Termination Check:

   • First, we check if k < |locations[i] - locations[finish]|
   • This means we don't have enough fuel to reach the finish even by the most direct route
   • If true, return 0 as no valid routes exist from this state

2. Initialize Route Count:

   • Set ans = 1 if i == finish (we're already at the destination), otherwise ans = 0
   • This accounts for the current position being a valid route if it's the finish

3. Explore All Possible Moves:

   • Iterate through all cities j using enumerate(locations)
   • For each city j where j != i:
     • Calculate fuel cost: |locations[i] - locations[j]|
     • Recursively call dfs(j, k - fuel_cost) to get routes from the new position
     • Add the result to ans (with modulo operation to prevent overflow)

4. Memoization with @cache:

   • The @cache decorator automatically stores results of dfs(i, k) calls
   • When the same (i, k) state is encountered again, the cached result is returned immediately
   • This prevents redundant calculations and reduces time complexity significantly

Why This Works:

• The recursive structure naturally explores all possible paths
• Each valid route that reaches the finish contributes 1 to the total count
• By summing contributions from all possible next moves, we count every unique route exactly once
• The memoization ensures we compute each unique state (city, fuel) only once, even though many different paths might lead to the same state

Time Complexity: O(n² × fuel) where n is the number of cities, as we have at most n × fuel states and each state examines n cities.

Space Complexity: O(n × fuel) for the memoization cache and recursion stack.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Input:

• locations = [2, 3, 6, 8, 4] (city positions)
• start = 1 (starting at city index 1, position 3)
• finish = 3 (destination at city index 3, position 8)
• fuel = 5

Step-by-Step DFS Exploration:

Starting with dfs(1, 5) - we're at city 1 (position 3) with 5 fuel:

1. Early termination check: Distance to finish = |3 - 8| = 5. We have exactly 5 fuel, so we can potentially reach it.

2. Initialize count: Since we're not at finish (1 ≠ 3), ans = 0

3. Explore moves from city 1:

   • To city 0 (position 2): costs |3 - 2| = 1 fuel → call dfs(0, 4)
   • To city 2 (position 6): costs |3 - 6| = 3 fuel → call dfs(2, 2)
   • To city 3 (position 8): costs |3 - 8| = 5 fuel → call dfs(3, 0)
   • To city 4 (position 4): costs |3 - 4| = 1 fuel → call dfs(4, 4)

Following one branch - dfs(3, 0):

• We're at city 3 (the finish!) with 0 fuel
• Early termination check: Distance to finish = 0, we have 0 fuel, so we pass
• Initialize count: Since we're at finish, ans = 1 (found one route!)
• Try to explore moves: With 0 fuel, we can't move anywhere
• Return 1

Following another branch - dfs(0, 4):

• We're at city 0 (position 2) with 4 fuel
• Early termination check: Distance to finish = |2 - 8| = 6, but we only have 4 fuel
• This means we can never reach the finish from here
• Return 0 immediately

Following dfs(2, 2):

• We're at city 2 (position 6) with 2 fuel
• Early termination check: Distance to finish = |6 - 8| = 2, we have exactly 2 fuel
• Initialize count: Not at finish, so ans = 0
• Explore moves:
  • To city 3 (position 8): costs |6 - 8| = 2 fuel → call dfs(3, 0) (returns 1)
  • Other moves cost too much fuel
• Return 1

Memoization in Action: When we call dfs(3, 0) from different paths (like from city 1 directly or via city 2), the second call returns the cached result immediately without recalculation.

Final Result: The total count accumulates from all valid paths. In this example, we find 2 valid routes:

1. City 1 → City 3 (direct route using all 5 fuel)
2. City 1 → City 2 → City 3 (using 3 + 2 = 5 fuel)

The function returns 2 as the total number of valid routes.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2 × m), where n is the size of the array locations and m is the value of fuel.

Time Complexity Analysis:

• The recursive function dfs(i, k) has at most n × m unique states, where i ranges from 0 to n-1 (representing different locations) and k ranges from 0 to m (representing remaining fuel).
• Due to the @cache decorator, each state is computed only once.
• For each state (i, k), the function iterates through all n locations to find possible next destinations, taking O(n) time.
• Therefore, the total time complexity is O(n × m) × O(n) = O(n^2 × m).

The space complexity is O(n × m).

Space Complexity Analysis:

• The @cache decorator stores the results of all computed states, which requires O(n × m) space to store all possible combinations of location index and remaining fuel.
• The recursion depth in the worst case could be O(m) (when we use 1 unit of fuel at each step), but this is dominated by the cache storage.
• Therefore, the total space complexity is O(n × m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Early Termination Logic

The Pitfall: A common mistake is to terminate early when remaining_fuel < abs(locations[current_city] - locations[finish]), thinking no valid routes exist. However, this optimization is actually incorrect for this problem.

Why It's Wrong: The finish city might not be the farthest city from our current position. Even if we can't reach the finish directly, we might be able to reach it through intermediate cities that are closer to us.

Example:

• Locations: [1, 5, 3], start=0 (position 1), finish=2 (position 3), fuel=3
• From city 0, direct distance to finish is |1-3|=2, which is feasible
• But if we had fuel=1, direct route is impossible (needs 2 fuel)
• However, we could still go 0→1 (cost |1-5|=4), which exceeds our fuel
• The early termination would incorrectly return 0 for some valid paths through closer intermediate cities

The Fix: Remove the early termination check entirely or make it more sophisticated:

@cache
def dfs(current_city: int, remaining_fuel: int) -> int:
    # Remove the incorrect early termination
    # if remaining_fuel < abs(locations[current_city] - locations[finish]):
    #     return 0
  
    route_count = 1 if current_city == finish else 0
  
    for next_city in range(len(locations)):
        if next_city != current_city:
            fuel_cost = abs(locations[current_city] - locations[next_city])
            # Only skip if we don't have enough fuel for this specific move
            if fuel_cost <= remaining_fuel:
                route_count = (route_count + dfs(next_city, remaining_fuel - fuel_cost)) % MOD
  
    return route_count

2. Forgetting to Check Fuel Before Making a Move

The Pitfall: Calling dfs(next_city, remaining_fuel - fuel_cost) without first checking if fuel_cost <= remaining_fuel, which could lead to exploring states with negative fuel.

Why It's Wrong: The problem explicitly states you cannot make a move if it would cause your fuel to become negative. Exploring negative fuel states violates the problem constraints.

The Fix: Always validate fuel sufficiency before making a recursive call:

for next_city in range(len(locations)):
    if next_city != current_city:
        fuel_cost = abs(locations[current_city] - locations[next_city])
        if fuel_cost <= remaining_fuel:  # Check fuel sufficiency first
            route_count = (route_count + dfs(next_city, remaining_fuel - fuel_cost)) % MOD

3. Forgetting the Modulo Operation

The Pitfall: Not applying modulo at each addition step, only applying it at the final return:

# Wrong approach
route_count = 1 if current_city == finish else 0
for next_city in range(len(locations)):
    if next_city != current_city and fuel_cost <= remaining_fuel:
        route_count += dfs(next_city, remaining_fuel - fuel_cost)
return route_count % MOD  # Only modulo at the end

Why It's Wrong: Integer overflow can occur during intermediate calculations before the final modulo operation, especially in languages with fixed integer sizes. Even in Python with arbitrary precision integers, it's good practice to apply modulo consistently.

The Fix: Apply modulo after each addition to keep numbers manageable:

route_count = (route_count + dfs(next_city, remaining_fuel - fuel_cost)) % MOD