Count All Possible Routes

Hard
1513.

Count All Possible Routes

Count All Possible Routes is a hard coding problem on arrays, dynamic programming and memoization, asked in Amazon and Google interviews.

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 <= 100
  • 1 <= locations[i] <= 10^9
  • all integers in locations are distinct
  • 0 <= start, finish < locations.length
  • 1 <= fuel <= 200
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} locations
 * @param {number} start
 * @param {number} finish
 * @param {number} fuel
 * @return {number}
 */
var countRoutes = function(locations, start, finish, fuel) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Count All Possible Routes

  1. 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.

  2. Hint 2

    Let ways(c, f) be the number of routes from city c to finish with f fuel. It is 1 if c == finish (stop here) plus the sum over every other city j you can afford to reach of ways(j, f - cost).

  3. 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

  1. Let ways[f][c] be the number of routes from city c that end at finish, having f fuel.
  2. For f from 0 to fuel and every city c: start with 1 if c == finish (the route may end right here), then add ways[f - d][j] for every city j != c with d = |locations[c] - locations[j]| <= f.
  3. Reduce modulo 10^9 + 7.
  4. 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 finish does 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