Count All Possible Routes - Practice Coding Problems

Count All Possible Routes - 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.

Input & Output

Example 1 — Basic Case

$ Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5

› Output: 4

💡 Note: Starting at city 1 (position 3) with 5 fuel, there are 4 possible routes to reach city 3 (position 8): 1→3 (cost 5), 1→0→3 (cost 1+6=7 > 5, invalid), 1→2→3 (cost 3+2=5), 1→4→3 (cost 1+4=5), and 1→4→0→3 (partial route within fuel limit).

Example 2 — Direct Route Only

$ Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6

› Output: 5

💡 Note: From city 1 (position 3) to city 0 (position 4) with 6 fuel, multiple paths exist including detours through city 2.

Example 3 — Insufficient Fuel

$ Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3

› Output: 0

💡 Note: From city 0 (position 5) to city 2 (position 1) requires 4 fuel minimum, but we only have 3.

Constraints

2 ≤ locations.length ≤ 100
1 ≤ locations[i] ≤ 10⁹
All integers in locations are distinct
0 ≤ start, finish < locations.length
1 ≤ fuel ≤ 200

Visualization

Tap to expand

Understanding the Visualization

Input

Cities at different positions with fuel limit

Process

Try all possible paths considering fuel costs

Output

Count of valid routes from start to finish

Key Takeaway

🎯 Key Insight: Same city with same remaining fuel always has the same number of possible routes to finish

Asked in

G Google 15 a Amazon 12 M Microsoft 8 A Apple 5

The key insight is that this is a path counting problem where we can revisit cities. Use memoization or bottom-up DP to avoid recalculating routes for the same (city, fuel) state. Best approach is memoization: Time O(n²×fuel), Space O(n×fuel).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization	O(n × fuel × n)	O(n × fuel)	Cache results to avoid recalculating same states
Bottom-Up Dynamic Programming	O(n² × fuel)	O(n × fuel)	Build solution iteratively using 2D DP table
Brute Force Recursion	O(n^fuel)	O(fuel)	Try all possible paths recursively without memoization

Memoization — Algorithm Steps

Create a memoization table for (city, fuel) states
For each state, try all possible moves to other cities
Cache and reuse results for previously computed states

Visualization

Tap to expand

Step-by-Step Walkthrough

Cache States

Store results for (city, fuel) combinations

Reuse Results

Check cache before calculating

Optimize

Avoid redundant computations

Code -

solution.c — C

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

const int MOD = 1000000007;
int memo[101][201]; // memo[city][fuel]
int memo_init[101][201];

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int dfs(int* locations, int n, int currentCity, int finish, int remainingFuel) {
    if (remainingFuel < 0) {
        return 0;
    }
    
    if (memo_init[currentCity][remainingFuel]) {
        return memo[currentCity][remainingFuel];
    }
    
    long long count = 0;
    if (currentCity == finish) {
        count = 1;
    }
    
    for (int nextCity = 0; nextCity < n; nextCity++) {
        if (nextCity != currentCity) {
            int cost = abs_val(locations[currentCity] - locations[nextCity]);
            if (remainingFuel >= cost) {
                count = (count + dfs(locations, n, nextCity, finish, remainingFuel - cost)) % MOD;
            }
        }
    }
    
    memo[currentCity][remainingFuel] = count;
    memo_init[currentCity][remainingFuel] = 1;
    return count;
}

int solution(int* locations, int n, int start, int finish, int fuel) {
    memset(memo_init, 0, sizeof(memo_init));
    return dfs(locations, n, start, finish, fuel);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int locations[100];
    int n = 0;
    char* token = strtok(line, "[],");
    while (token != NULL) {
        locations[n++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    
    int start, finish, fuel;
    scanf("%d %d %d", &start, &finish, &fuel);
    
    int result = solution(locations, n, start, finish, fuel);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × fuel × n)

For each of n×fuel states, we try n possible moves

✓ Linear Growth

Space Complexity

O(n × fuel)

Memoization table stores results for each (city, fuel) combination

⚡ Linearithmic Space

38.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler