Count All Possible Routes — Solution in Python, Java & C++
Count All Possible Routes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count All Possible Routes is a hard coding problem on arrays, dynamic programming and memoization, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Memoization
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of distinct positive integers locations, where locations[i] is the position of city i, together with the integers start, finish and fuel — your starting city, your destination and your initial fuel.
From city i you may drive to any other city j != i, which burns |locations[i] - locations[j]| units of fuel. Your fuel can never drop below zero. You may visit any city, including start and finish, as many times as you like.
Count the routes that begin at start and end at finish — a route is the sequence of cities visited, and it ends whenever you are at finish (it may also pass through finish earlier). If start == finish, the route that does not move counts too. Return the count modulo 10^9 + 7.
Example 1
Input: locations = [1,4,2], start = 0, finish = 1, fuel = 6
Output: 4
Explanation: `0→1`, `0→2→1`, `0→2→0→1` and `0→2→0→2→1`, using 3, 3, 5 and 5 units of fuel.
Example 2
Input: locations = [3,8], start = 1, finish = 1, fuel = 9
Output: 1
Explanation: Only the empty route: going to city 0 and back needs 10 units.
Example 3
Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: Even the direct drive needs 4 units.
Constraints
2 <= locations.length <= 1001 <= locations[i] <= 10^9all integers in locations are distinct0 <= start, finish < locations.length1 <= fuel <= 200
Hints for Count All Possible Routes
Hint 1
A route from a city depends only on where you are and how much fuel is left — not on how you got there.
Hint 2
Let
ways(c, f)be the number of routes from cityctofinishwithffuel. It is 1 ifc == finish(stop here) plus the sum over every other cityjyou can afford to reach ofways(j, f - cost).Hint 3
Every move costs at least 1 because the locations are distinct, so fill the table by increasing fuel: each entry only reads entries with less fuel.
How to solve Count All Possible Routes
Count routes by state (city, fuel left). Because cities have distinct positions, every move strictly lowers the fuel, so the states form a DAG ordered by fuel and a table filled from low fuel to high fuel counts every route exactly once.
Approach
- Let
ways[f][c]be the number of routes from citycthat end atfinish, havingffuel. - For
ffrom 0 tofueland every cityc: start with 1 ifc == finish(the route may end right here), then addways[f - d][j]for every cityj != cwithd = |locations[c] - locations[j]| <= f. - Reduce modulo 10^9 + 7.
- Return
ways[fuel][start].
Why it works
A route from c either ends immediately (possible only at finish) or makes a first move to some j, after which it is an arbitrary route from j with the remaining fuel. These cases are disjoint and cover every route, which is the recurrence. Since d >= 1, ways[f - d] is already computed when row f is filled.
Complexity
- Time —
O(n^2 · fuel) - Space —
O(n · fuel)
Pitfalls
- Passing through
finishdoes not end the route — routes that continue past it and return later are counted separately. - When
start == finish, the zero-move route counts. - The sums exceed 32 bits before the modulus; accumulate in 64-bit integers.
Reference solution
Python
from typing import List
def countRoutes(locations: List[int], start: int, finish: int, fuel: int) -> int:
MOD = 10 ** 9 + 7
n = len(locations)
ways = [[0] * n for _ in range(fuel + 1)]
for f in range(fuel + 1):
for c in range(n):
total = 1 if c == finish else 0
for j in range(n):
if j != c:
d = abs(locations[c] - locations[j])
if d <= f:
total += ways[f - d][j]
ways[f][c] = total % MOD
return ways[fuel][start]Java
public static int countRoutes(int[] locations, int start, int finish, int fuel) {
final long MOD = 1000000007L;
int n = locations.length;
long[][] ways = new long[fuel + 1][n];
for (int f = 0; f <= fuel; f++) {
for (int c = 0; c < n; c++) {
long total = c == finish ? 1 : 0;
for (int j = 0; j < n; j++) {
if (j == c) continue;
int d = Math.abs(locations[c] - locations[j]);
if (d <= f) total += ways[f - d][j];
}
ways[f][c] = total % MOD;
}
}
return (int) ways[fuel][start];
}C++
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
const long long MOD = 1000000007LL;
int n = locations.size();
vector<vector<long long>> ways(fuel + 1, vector<long long>(n, 0));
for (int f = 0; f <= fuel; f++) {
for (int c = 0; c < n; c++) {
long long total = c == finish ? 1 : 0;
for (int j = 0; j < n; j++) {
if (j == c) continue;
int d = abs(locations[c] - locations[j]);
if (d <= f) total += ways[f - d][j];
}
ways[f][c] = total % MOD;
}
}
return (int)ways[fuel][start];
}JavaScript
var countRoutes = function(locations, start, finish, fuel) {
var MOD = 1000000007, n = locations.length;
var ways = [];
for (var f = 0; f <= fuel; f++) {
ways.push(new Array(n).fill(0));
for (var c = 0; c < n; c++) {
var total = c === finish ? 1 : 0;
for (var j = 0; j < n; j++) {
if (j === c) continue;
var d = Math.abs(locations[c] - locations[j]);
if (d <= f) total += ways[f - d][j];
}
ways[f][c] = total % MOD;
}
}
return ways[fuel][start];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming