1575. Count All Possible Routes - Solution

The problem

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 10⁹ + 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] <= 10⁹
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

Approach overview

Problem 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 1: Dynamic Programming with Memoization

This approach involves using dynamic programming to keep track of the number of ways to reach the target city with the available fuel. We will define a DP table where dp[i][f] represents the number of ways to start from city i with f units of fuel left and reach the target city. We recursively fill this table while considering moves to any other city and subtracting the appropriate fuel cost for that move. The result will be stored in the dp[start][fuel] after exploring all possible routes.

Python

class CountRoutes:
    MOD = 10**9 + 7

    def __init__(self):
        self.dp = []

    def countRoutes(self, locations, start, finish, fuel):
        n = len(locations)
        self.dp = [[-1] * (fuel + 1) for _ in range(n)]
        return self.countRoutesUtil(locations, start, finish, fuel)

    def countRoutesUtil(self, locations, curr, finish, fuel):
        if fuel < 0:
            return 0
        if self.dp[curr][fuel] != -1:
            return self.dp[curr][fuel]

        result = 1 if curr == finish else 0
        for i in range(len(locations)):
            if i != curr:
                result = (result + self.countRoutesUtil(locations, i, finish, fuel - abs(locations[i] - locations[curr]))) % self.MOD

        self.dp[curr][fuel] = result
        return result

# Example usage
challenge = CountRoutes()
locations = [2, 3, 6, 8, 4]
start, finish, fuel = 1, 3, 5
print(challenge.countRoutes(locations, start, finish, fuel))  # Output: 4

Java

import java.util.*;

public class CountRoutes {
    private static final int MOD = 1000000007;
    private int[][] dp;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        dp = new int[locations.length][fuel + 1];
        for (int[] d : dp) Arrays.fill(d, -1);
        return countRoutesUtil(locations, start, finish, fuel);
    }

    private int countRoutesUtil(int[] locations, int curr, int finish, int fuel) {
        if (fuel < 0) return 0;
        if (dp[curr][fuel] != -1) return dp[curr][fuel];

        int result = (curr == finish) ? 1 : 0;
        for (int i = 0; i < locations.length; ++i) {
            if (i != curr) {
                result = (result + countRoutesUtil(locations, i, finish, fuel - Math.abs(locations[i] - locations[curr]))) % MOD;
            }
        }
        return dp[curr][fuel] = result;
    }

    public static void main(String[] args) {
        CountRoutes obj = new CountRoutes();
        int[] locations = {2, 3, 6, 8, 4};
        int start = 1, finish = 3, fuel = 5;
        System.out.println(obj.countRoutes(locations, start, finish, fuel)); // Output: 4
    }
}

C++

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MOD = 1000000007;

int dp[101][201];

int countRoutesUtil(vector<int> &locations, int curr, int finish, int fuel) {
    if (fuel < 0) return 0;
    if (dp[curr][fuel] != -1) return dp[curr][fuel];

    int result = (curr == finish) ? 1 : 0;
    for (int i = 0; i < locations.size(); ++i) {
        if (i != curr) {
            result = (result + countRoutesUtil(locations, i, finish, fuel - abs(locations[i] - locations[curr]))) % MOD;
        }
    }
    return dp[curr][fuel] = result;
}

int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
    memset(dp, -1, sizeof(dp));
    return countRoutesUtil(locations, start, finish, fuel);
}

int main() {
    vector<int> locations = {2, 3, 6, 8, 4};
    int start = 1, finish = 3, fuel = 5;
    cout << countRoutes(locations, start, finish, fuel) << endl; // Output: 4
    return 0;
}

JavaScript

const MOD = 1000000007;

var countRoutes = function(locations, start, finish, fuel) {
    const dp = Array.from({ length: locations.length }, () => Array(fuel + 1).fill(-1));
    const countRoutesUtil = (current, fuelLeft) => {
        if (fuelLeft < 0) return 0;
        if (dp[current][fuelLeft] !== -1) return dp[current][fuelLeft];

        let result = (current === finish) ? 1 : 0;
        for (let i = 0; i < locations.length; i++) {
            if (i !== current) {
                result = (result + countRoutesUtil(i, fuelLeft - Math.abs(locations[i] - locations[current]))) % MOD;
            }
        }

        dp[current][fuelLeft] = result;
        return result;
    };

    return countRoutesUtil(start, fuel);
};

const locations = [2, 3, 6, 8, 4];
const start = 1;
const finish = 3;
const fuel = 5;
console.log(countRoutes(locations, start, finish, fuel)); // Output: 4

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int dp[101][201];

int countRoutesUtil(int* locations, int n, int curr, int finish, int fuel) {
    if (fuel < 0) return 0;
    if (dp[curr][fuel] != -1) return dp[curr][fuel];

    int result = (curr == finish) ? 1 : 0;
    for (int i = 0; i < n; ++i) {
        if (i != curr) {
            result = (result + countRoutesUtil(locations, n, i, finish, fuel - abs(locations[i] - locations[curr]))) % MOD;
        }
    }
    return dp[curr][fuel] = result;
}

int countRoutes(int* locations, int locationsSize, int start, int finish, int fuel) {
    memset(dp, -1, sizeof(dp));
    return countRoutesUtil(locations, locationsSize, start, finish, fuel);
}

int main() {
    int locations[] = {2, 3, 6, 8, 4};
    int start = 1, finish = 3, fuel = 5;
    printf("%d\n", countRoutes(locations, 5, start, finish, fuel)); // Output: 4
    return 0;
}

using System;

class CountRoutes {
    const int MOD = 1000000007;
    int[,] dp;

    public int CalculateRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.Length;
        dp = new int[n, fuel + 1];
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= fuel; j++)
                dp[i, j] = -1;
        return CountRoutesUtil(locations, start, finish, fuel);
    }

    private int CountRoutesUtil(int[] locations, int curr, int finish, int fuel) {
        if (fuel < 0) return 0;
        if (dp[curr, fuel] != -1) return dp[curr, fuel];

        int result = (curr == finish) ? 1 : 0;
        for (int i = 0; i < locations.Length; ++i) {
            if (i != curr) {
                result = (result + CountRoutesUtil(locations, i, finish, fuel - Math.Abs(locations[i] - locations[curr]))) % MOD;
            }
        }
        return dp[curr, fuel] = result;
    }

    static void Main() {
        int[] locations = {2, 3, 6, 8, 4};
        int start = 1, finish = 3, fuel = 5;
        CountRoutes obj = new CountRoutes();
        Console.WriteLine(obj.CalculateRoutes(locations, start, finish, fuel)); // Output: 4
    }
}

The Python implementation uses a class to store the DP table and facilitates direct recursion with memoization. It iterates over options in recursive calls while updating the DP table and returns results modulo 10^9 + 7.

Complexity

Time Complexity: O(n * fuel * n).
Space Complexity: O(n * fuel) for the DP table.

Try this approach in the editor

Approach 2: Recursive Depth-First Search

In this approach, a depth-first search (DFS) is implemented to explore possible routes from the start to the finish city. Each travel option is a branch in the DFS tree, where the algorithm explores each choice of stopping at a different city until it no longer has fuel. The recursion keeps track of current fuel and updates the count whenever it reaches the finish city with valid fuel.

Python

class DFSSolution:
    MOD = 10**9 + 7

    def countRoutes(self, locations, start, finish, fuel):
        return self.countRoutesDFS(locations, start, finish, fuel)

    def countRoutesDFS(self, locations, curr, finish, fuel):
        if fuel < 0:
            return 0

        result = 1 if curr == finish else 0
        for i in range(len(locations)):
            if i != curr:
                result = (result + self.countRoutesDFS(locations, i, finish, fuel - abs(locations[i] - locations[curr]))) % self.MOD

        return result

# Example usage
solver = DFSSolution()
locations = [2, 3, 6, 8, 4]
print(solver.countRoutes(locations, 1, 3, 5))  # Output: 4

Java

import java.util.*;

public class DFSCountRoutes {
    private static final int MOD = 1000000007;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        return countRoutesDFS(locations, start, finish, fuel);
    }

    private int countRoutesDFS(int[] locations, int curr, int finish, int fuel) {
        if (fuel < 0) return 0;
        int result = (curr == finish) ? 1 : 0;
        for (int i = 0; i < locations.length; ++i) {
            if (i != curr) {
                result = (result + countRoutesDFS(locations, i, finish, fuel - Math.abs(locations[i] - locations[curr]))) % MOD;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        DFSCountRoutes obj = new DFSCountRoutes();
        int[] locations = {2, 3, 6, 8, 4};
        System.out.println(obj.countRoutes(locations, 1, 3, 5)); // Output: 4
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int countRoutesDFS(vector<int> &locations, int curr, int finish, int fuel) {
    if (fuel < 0) return 0;
    int result = (curr == finish) ? 1 : 0;
    for (int i = 0; i < locations.size(); ++i) {
        if (i != curr) {
            result = (result + countRoutesDFS(locations, i, finish, fuel - abs(locations[i] - locations[curr]))) % MOD;
        }
    }
    return result;
}

int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
    return countRoutesDFS(locations, start, finish, fuel);
}

int main() {
    vector<int> locations = {2, 3, 6, 8, 4};
    cout << countRoutes(locations, 1, 3, 5) << endl; // Output: 4
    return 0;
}

JavaScript

const MOD = 1000000007;

function countRoutes(locations, start, finish, fuel) {
    function dfs(current, remainingFuel) {
        if (remainingFuel < 0) return 0;

        let result = (current === finish) ? 1 : 0;
        for (let i = 0; i < locations.length; i++) {
            if (i !== current) {
                result = (result + dfs(i, remainingFuel - Math.abs(locations[i] - locations[current]))) % MOD;
            }
        }

        return result;
    }

    return dfs(start, fuel);
}

const locations = [2, 3, 6, 8, 4];
console.log(countRoutes(locations, 1, 3, 5)); // Output: 4

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007

int countRoutesDFS(int* locations, int n, int curr, int finish, int fuel) {
    if (fuel < 0) return 0;
    int result = (curr == finish) ? 1 : 0;
    for (int i = 0; i < n; ++i) {
        if (i != curr) {
            result = (result + countRoutesDFS(locations, n, i, finish, fuel - abs(locations[i] - locations[curr]))) % MOD;
        }
    }
    return result;
}

int countRoutes(int* locations, int locationsSize, int start, int finish, int fuel) {
    return countRoutesDFS(locations, locationsSize, start, finish, fuel);
}

int main() {
    int locations[] = {2, 3, 6, 8, 4};
    printf("%d\n", countRoutes(locations, 5, 1, 3, 5)); // Output: 4
    return 0;
}

using System;

class DFSCountRoutes {
    const int MOD = 1000000007;

    public int CountRoutes(int[] locations, int start, int finish, int fuel) {
        return countRoutesDFS(locations, start, finish, fuel);
    }

    private int countRoutesDFS(int[] locations, int curr, int finish, int fuel) {
        if (fuel < 0) return 0;
        int result = (curr == finish) ? 1 : 0;
        for (int i = 0; i < locations.Length; i++) {
            if (i != curr) {
                result = (result + countRoutesDFS(locations, i, finish, fuel - Math.Abs(locations[i] - locations[curr]))) % MOD;
            }
        }
        return result;
    }

    static void Main() {
        int[] locations = {2, 3, 6, 8, 4};
        DFSCountRoutes obj = new DFSCountRoutes();
        Console.WriteLine(obj.CountRoutes(locations, 1, 3, 5)); // Output: 4
    }
}

The Python version follows the DFS model traversing each potential path recursively. Without memoization, this may lead to computational redundancy but provides clear path evaluations.

Complexity

Time Complexity: O(n^fuel), considered high due to exponential breadth per fuel level.
Space Complexity: O(fuel).

Try this approach in the editor

Approach 3: Memoization

We design a function dfs(i, k), which represents the number of paths from city i with k remaining fuel to the destination finish. So the answer is dfs(start, fuel).

The process of calculating the function dfs(i, k) is as follows:

If k \lt |locations[i] - locations[finish]|, then return 0.
If i = finish, then the number of paths is 1 at the beginning, otherwise it is 0.
Then, we traverse all cities j. If j \ne i, then we can move from city i to city j, and the remaining fuel is k - |locations[i] - locations[j]|. Then we can add the number of paths to the answer dfs(j, k - |locations[i] - locations[j]|).
Finally, we return the number of paths to the answer.

To avoid repeated calculations, we can use memoization.

The time complexity is O(n^2 times m), and the space complexity is O(n times m). Where n and m are the size of the array locations and fuel respectively.

TypeScript

function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
    const n = locations.length;
    const f = Array.from({ length: n }, () => Array(fuel + 1).fill(-1));
    const mod = 1e9 + 7;
    const dfs = (i: number, k: number): number => {
        if (k < Math.abs(locations[i] - locations[finish])) {
            return 0;
        }
        if (f[i][k] !== -1) {
            return f[i][k];
        }
        let ans = i === finish ? 1 : 0;
        for (let j = 0; j < n; ++j) {
            if (j !== i) {
                const x = Math.abs(locations[i] - locations[j]);
                ans = (ans + dfs(j, k - x)) % mod;
            }
        }
        return (f[i][k] = ans);
    };
    return dfs(start, fuel);
}

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, fuel+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	const mod = 1e9 + 7
	var dfs func(int, int) int
	dfs = func(i, k int) (ans int) {
		if k < abs(locations[i]-locations[finish]) {
			return 0
		}
		if f[i][k] != -1 {
			return f[i][k]
		}
		if i == finish {
			ans = 1
		}
		for j, x := range locations {
			if j != i {
				ans = (ans + dfs(j, k-abs(locations[i]-x))) % mod
			}
		}
		f[i][k] = ans
		return
	}
	return dfs(start, fuel)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Try this approach in the editor

Approach 4: Dynamic Programming

We can also convert the memoization of solution 1 into dynamic programming.

We define f[i][k] represents the number of paths from city i with k remaining fuel to the destination finish. So the answer is f[start][fuel]. Initially f[finish][k]=1, others are 0.

Next, we enumerate the remaining fuel k from small to large, and then enumerate all cities i. For each city i, we enumerate all cities j. If j \ne i, and |locations[i] - locations[j]| \le k, then we can move from city i to city j, and the remaining fuel is k - |locations[i] - locations[j]|. Then we can add the number of paths to the answer f[j][k - |locations[i] - locations[j]|].

Finally, we return the number of paths to the answer f[start][fuel].

The time complexity is O(n^2 times m), and the space complexity is O(n times m). Where n and m are the size of the array locations and fuel respectively.

TypeScript

function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
    const n = locations.length;
    const f = Array.from({ length: n }, () => Array(fuel + 1).fill(0));
    for (let k = 0; k <= fuel; ++k) {
        f[finish][k] = 1;
    }
    const mod = 1e9 + 7;
    for (let k = 0; k <= fuel; ++k) {
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                if (j !== i && Math.abs(locations[i] - locations[j]) <= k) {
                    f[i][k] = (f[i][k] + f[j][k - Math.abs(locations[i] - locations[j])]) % mod;
                }
            }
        }
    }
    return f[start][fuel];
}

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	const mod = 1e9 + 7
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, fuel+1)
	}
	for k := 0; k <= fuel; k++ {
		f[finish][k] = 1
	}
	for k := 0; k <= fuel; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if j != i && abs(locations[i]-locations[j]) <= k {
					f[i][k] = (f[i][k] + f[j][k-abs(locations[i]-locations[j])]) % mod
				}
			}
		}
	}
	return f[start][fuel]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Memoization	Time Complexity: O(n * fuel * n). Space Complexity: O(n * fuel) for the DP table.
Recursive Depth-First Search	Time Complexity: O(n^fuel), considered high due to exponential breadth per fuel level. Space Complexity: O(fuel).
Memoization	–
Dynamic Programming	–

Complexity analysis

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

Frequently asked questions

Is Count All Possible Routes easy or hard?

Count All Possible Routes is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the DP state (city, fuel) and handling repeated visits to cities without exponential recomputation.

Count All Possible Routes Python/Java solution

Both Python and Java solutions typically implement DFS with memoization. A recursive function explores possible next cities, stores results in a dp table, and returns cached results when the same state appears again.

How to solve Count All Possible Routes in O(n^2 * fuel)?

Use DFS with memoization. Define a function dfs(city, fuel) that returns the number of routes from that city with the remaining fuel. Cache results in a DP table and iterate through every other city to explore valid moves whose travel cost fits within the remaining fuel.

What is the best approach for Count All Possible Routes?

Dynamic Programming with memoization is the best approach. The state is defined by the current city and remaining fuel, and results are cached in a dp[city][fuel] table. This prevents recalculating identical states and reduces the complexity to O(n^2 * fuel).

Is Count All Possible Routes asked at Google/Amazon/Meta?

Dynamic programming problems involving state transitions and memoization frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests recognizing overlapping subproblems and designing an efficient DP state.

What data structure is used in Count All Possible Routes?

The main structure is a 2D dynamic programming array or memoization table dp[city][fuel]. Recursion or DFS is used to explore transitions, while the array caches previously computed states.

What is the time complexity of Count All Possible Routes?

The optimized solution runs in O(n^2 * fuel) time because for each state (city, remaining fuel) you iterate through all other cities. The space complexity is O(n * fuel) for the memoization table.

Count All Possible Routes solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Memoization

Approach 2: Recursive Depth-First Search

Approach 3: Memoization

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count All Possible Routes solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Memoization

Approach 2: Recursive Depth-First Search

Approach 3: Memoization

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems