LeetCode #1575 — HARD

Count All Possible Routes

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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

Step 01

Brute Force Baseline

Problem summary: 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 109 + 7.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Dynamic Programming

Example 1

[2,3,6,8,4]
1
3
5

Example 2

[4,3,1]
1
0
6

Example 3

[5,2,1]
0
2
3

Step 02

Core Insight

What unlocks the optimal approach

Use dynamic programming to solve this problem with each state defined by the city index and fuel left.
Since the array contains distinct integers fuel will always be spent in each move and so there can be no cycles.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1575: Count All Possible Routes
class Solution {
    private int[] locations;
    private int finish;
    private int n;
    private Integer[][] f;
    private final int mod = (int) 1e9 + 7;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        n = locations.length;
        this.locations = locations;
        this.finish = finish;
        f = new Integer[n][fuel + 1];
        return dfs(start, fuel);
    }

    private int dfs(int i, int k) {
        if (k < Math.abs(locations[i] - locations[finish])) {
            return 0;
        }
        if (f[i][k] != null) {
            return f[i][k];
        }
        int ans = i == finish ? 1 : 0;
        for (int j = 0; j < n; ++j) {
            if (j != i) {
                ans = (ans + dfs(j, k - Math.abs(locations[i] - locations[j]))) % mod;
            }
        }
        return f[i][k] = ans;
    }
}

// Accepted solution for LeetCode #1575: Count All Possible Routes
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
}

# Accepted solution for LeetCode #1575: Count All Possible Routes
class Solution:
    def countRoutes(
        self, locations: List[int], start: int, finish: int, fuel: int
    ) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if k < abs(locations[i] - locations[finish]):
                return 0
            ans = int(i == finish)
            for j, x in enumerate(locations):
                if j != i:
                    ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod
            return ans

        mod = 10**9 + 7
        return dfs(start, fuel)

// Accepted solution for LeetCode #1575: Count All Possible Routes
struct Solution;

use std::collections::HashMap;

const MOD: i64 = 1_000_000_007;

impl Solution {
    fn count_routes(locations: Vec<i32>, start: i32, finish: i32, fuel: i32) -> i32 {
        let n = locations.len();
        let mut memo: HashMap<(usize, i32), i64> = HashMap::new();
        let start = start as usize;
        let finish = finish as usize;
        memo.insert((start, fuel), 1);
        ((0..=fuel)
            .map(|f| Self::dp(finish, f, &mut memo, &locations, fuel, n))
            .sum::<i64>()
            % MOD) as i32
    }

    fn dp(
        i: usize,
        fuel: i32,
        memo: &mut HashMap<(usize, i32), i64>,
        locations: &[i32],
        max_fuel: i32,
        n: usize,
    ) -> i64 {
        if fuel > max_fuel {
            return 0;
        }
        if let Some(&res) = memo.get(&(i, fuel)) {
            return res;
        }
        let mut res = 0;
        for j in 0..n {
            if i != j {
                let cost = (locations[i] - locations[j]).abs();
                res += Self::dp(j, fuel + cost, memo, locations, max_fuel, n);
                res %= MOD;
            }
        }
        memo.insert((i, fuel), res);
        res
    }
}

#[test]
fn test() {
    let locations = vec![2, 3, 6, 8, 4];
    let start = 1;
    let finish = 3;
    let fuel = 5;
    let res = 4;
    assert_eq!(Solution::count_routes(locations, start, finish, fuel), res);
    let locations = vec![4, 3, 1];
    let start = 1;
    let finish = 0;
    let fuel = 6;
    let res = 5;
    assert_eq!(Solution::count_routes(locations, start, finish, fuel), res);
    let locations = vec![5, 2, 1];
    let start = 0;
    let finish = 2;
    let fuel = 3;
    let res = 0;
    assert_eq!(Solution::count_routes(locations, start, finish, fuel), res);
    let locations = vec![2, 1, 5];
    let start = 0;
    let finish = 0;
    let fuel = 3;
    let res = 2;
    assert_eq!(Solution::count_routes(locations, start, finish, fuel), res);
    let locations = vec![1, 2, 3];
    let start = 0;
    let finish = 2;
    let fuel = 40;
    let res = 615088286;
    assert_eq!(Solution::count_routes(locations, start, finish, fuel), res);
}

// Accepted solution for LeetCode #1575: Count All Possible Routes
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);
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n^2 × m)

Space

O(n × m)

Approach Breakdown

RECURSIVE

O(2ⁿ) time

O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING

O(n × m) time

O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.