LeetCode Problem 1575

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Memoization

Solution

LeetCode 1575 - Count All Possible Routes

Problem Understanding

This problem gives us a set of cities positioned on a number line. The array locations stores the coordinate of each city, where locations[i] represents the position of city i.

We are also given:

• start, the index of the city where we begin
• finish, the index of the destination city
• fuel, the total amount of fuel available

Moving from city i to city j costs:

$|locations[i]-locations[j]|$

units of fuel.

The task is not to find the shortest route or a single valid route. Instead, we must count every possible route that starts at start and ends at finish, as long as the fuel never becomes negative.

A route may revisit cities multiple times, including the start and finish cities. This detail is extremely important because it means cycles are allowed. For example, a route like:

0 -> 1 -> 0 -> 1 -> 2

is completely valid if enough fuel exists.

The answer can become very large, so we return it modulo:

$10^9+7$

The constraints reveal important information about the expected solution:

Constraint	Meaning
locations.length <= 100	We can potentially examine transitions between every pair of cities
fuel <= 200	Fuel is small enough for dynamic programming over fuel states
Coordinates up to 10^9	We should never build coordinate-based grids
Cities are distinct	Distance between different cities is always positive

The most important edge cases are:

• The start city may already equal the finish city. In this case, staying at the city counts as one valid route.
• It may be impossible to reach the destination even once.
• Because revisits are allowed, naive recursion can explode exponentially.
• Many different paths can reach the same (city, remainingFuel) state, which strongly suggests memoization or dynamic programming.

Approaches

Brute Force Approach

A brute force solution would recursively try every possible next city from the current city.

From city i, we attempt to move to every other city j where the fuel cost is affordable. After moving, we recursively continue exploring routes from j.

Whenever we arrive at finish, we count one valid route.

This approach is correct because it explicitly enumerates every valid sequence of moves.

However, it is far too slow. Since cities may be revisited repeatedly, the number of possible paths grows exponentially with the fuel amount. The recursion repeatedly recalculates the same states.

For example, suppose we reach:

(city = 2, fuel = 7)

through multiple different paths. The brute force solution recomputes all future possibilities from this state every time.

This overlapping subproblem structure makes brute force inefficient.

Optimal Approach, Dynamic Programming with Memoization

The key observation is that the future possibilities depend only on:

• the current city
• the remaining fuel

Nothing else matters.

This means we can define a DP state:

dp(city, remainingFuel)

which represents the number of valid routes from the current city to the destination using at most remainingFuel.

Once we compute this value once, we can reuse it everywhere else.

The recurrence is:

• If the current city equals finish, count one route immediately.
• Then try moving to every other city that is reachable with the remaining fuel.
• Add all recursive results together.

Memoization prevents repeated work, reducing the complexity dramatically.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(fuel) recursion depth	Recomputes identical states many times
Optimal	O(n² × fuel)	O(n × fuel)	Uses memoization for overlapping subproblems

Algorithm Walkthrough

1. Define a recursive function dfs(city, remainingFuel).

This function returns the number of valid routes starting from city with remainingFuel fuel left. 2. Use memoization to cache computed states.

Since many paths can lead to the same state, memoization prevents repeated computation. 3. Initialize the answer for the current state.

If city == finish, then staying at the destination already forms one valid route. 4. Try traveling to every other city.

For each city nextCity:

• Skip if nextCity == city
• Compute fuel cost:

$cost=|locations[city]-locations[nextCity]|$

• If enough fuel remains, recursively explore:

dfs(nextCity, remainingFuel - cost)

5. Add all valid recursive results together.

Since the result can become huge, take modulo 10^9 + 7 after additions. 6. Return the memoized result.

Why It Works

The algorithm works because every valid route can be decomposed into:

• the current city
• one next move
• all valid routes from the next state

The recursion explores every legal transition exactly once per DP state. Memoization guarantees that identical states are not recomputed, while still counting every distinct route.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def countRoutes(
        self,
        locations: List[int],
        start: int,
        finish: int,
        fuel: int
    ) -> int:
        MOD = 10**9 + 7
        n = len(locations)

        @lru_cache(None)
        def dfs(city: int, remaining_fuel: int) -> int:
            routes = 1 if city == finish else 0

            for next_city in range(n):
                if next_city == city:
                    continue

                fuel_cost = abs(
                    locations[city] - locations[next_city]
                )

                if fuel_cost <= remaining_fuel:
                    routes += dfs(
                        next_city,
                        remaining_fuel - fuel_cost
                    )

            return routes % MOD

        return dfs(start, fuel)

The implementation starts by defining constants and retrieving the number of cities.

The recursive dfs function represents the DP state. The memoization decorator @lru_cache(None) stores results for every (city, remaining_fuel) pair.

Inside the function, we first count the current state as one valid route if the current city equals the destination. This is important because reaching the destination at any time counts immediately, even if additional fuel remains for more travel.

The loop then attempts transitions to every other city. The fuel cost is computed using the absolute distance between coordinates.

If enough fuel exists, the recursion continues with reduced fuel.

Finally, the result is returned modulo 10^9 + 7.

Go Solution

package main

func countRoutes(locations []int, start int, finish int, fuel int) int {
	const MOD int = 1_000_000_007

	n := len(locations)

	memo := make([][]int, n)
	for i := 0; i < n; i++ {
		memo[i] = make([]int, fuel+1)
		for j := 0; j <= fuel; j++ {
			memo[i][j] = -1
		}
	}

	var dfs func(city int, remainingFuel int) int

	dfs = func(city int, remainingFuel int) int {
		if memo[city][remainingFuel] != -1 {
			return memo[city][remainingFuel]
		}

		routes := 0

		if city == finish {
			routes = 1
		}

		for nextCity := 0; nextCity < n; nextCity++ {
			if nextCity == city {
				continue
			}

			cost := locations[city] - locations[nextCity]
			if cost < 0 {
				cost = -cost
			}

			if cost <= remainingFuel {
				routes += dfs(nextCity, remainingFuel-cost)
				routes %= MOD
			}
		}

		memo[city][remainingFuel] = routes
		return routes
	}

	return dfs(start, fuel)
}

The Go solution uses a 2D slice memo instead of Python's lru_cache.

Each entry stores the computed answer for:

(city, remainingFuel)

Uncomputed states are initialized to -1.

Go does not provide a built in absolute value function for integers, so the distance calculation is handled manually.

Modulo operations are applied during accumulation to avoid integer overflow.

Worked Examples

Example 1

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

City coordinates:

City	Position
0	2
1	3
2	6
3	8
4	4

We begin at city 1 with fuel 5.

Step-by-step exploration

Current Path	Fuel Left	Valid?
1 -> 3	0	Yes
1 -> 2 -> 3	0	Yes
1 -> 4 -> 3	0	Yes
1 -> 4 -> 2 -> 3	0	Yes

The algorithm counts all four routes.

Final answer:

4

Example 2

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

Distances:

From	To	Cost
1	0	1
1	2	2
0	1	1
2	1	2

Possible valid routes:

Route	Fuel Used
1 -> 0	1
1 -> 2 -> 0	5
1 -> 2 -> 1 -> 0	5
1 -> 0 -> 1 -> 0	3
1 -> 0 -> 1 -> 0 -> 1 -> 0	5

Total routes:

5

Example 3

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

Shortest possible movement:

Move	Cost
0 -> 2	4

Since fuel is only 3, no route is possible.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² × fuel)	Each DP state examines every other city
Space	O(n × fuel)	Memoization table stores all states

There are at most:

$n\times(fuel+1)$

distinct states.

For each state, we iterate through all n cities to test transitions. Therefore the total complexity becomes:

$O(n^2\times fuel)$

The recursion stack depth is bounded by the fuel amount because every move consumes positive fuel.

Test Cases

sol = Solution()

# Example 1
assert sol.countRoutes([2,3,6,8,4], 1, 3, 5) == 4

# Example 2
assert sol.countRoutes([4,3,1], 1, 0, 6) == 5

# Example 3
assert sol.countRoutes([5,2,1], 0, 2, 3) == 0

# Start already equals finish
assert sol.countRoutes([1,2,3], 0, 0, 1) == 1

# Single direct route
assert sol.countRoutes([1,5], 0, 1, 4) == 1

# Not enough fuel
assert sol.countRoutes([1,10], 0, 1, 5) == 0

# Multiple revisits possible
assert sol.countRoutes([1,2,3], 0, 2, 4) == 6

# Minimum fuel
assert sol.countRoutes([1,2], 0, 1, 1) == 1

# Large fuel with cycles
assert sol.countRoutes([1,3,5], 0, 2, 10) > 0

# Destination unreachable despite many cities
assert sol.countRoutes([1,100,200,300], 0, 3, 50) == 0

Test Case Summary

Test	Why
Example 1	Basic multi-path scenario
Example 2	Verifies cycles and revisits
Example 3	Destination unreachable
start == finish	Staying immediately counts as a route
Two-city direct route	Simplest successful transition
Insufficient fuel	Ensures impossible paths return zero
Multiple revisits	Tests repeated-state handling
Minimum fuel	Boundary constraint
Large fuel	Stress test for memoization
Large coordinate gaps	Confirms distance handling

Edge Cases

Start City Equals Finish City

One subtle detail is that the starting city itself counts as a valid route if start == finish.

For example:

locations = [1, 2, 3]
start = 0
finish = 0
fuel = 0

Even without moving, the answer should be 1.

A common bug is forgetting to count the current state immediately when the current city equals the destination. The implementation handles this correctly by initializing:

routes = 1 if city == finish else 0

inside every DP state.

Cycles and Revisited Cities

The problem explicitly allows revisiting cities. This creates cycles in the state graph.

For example:

0 -> 1 -> 0 -> 1 -> 2

A naive DFS without memoization becomes exponentially slow because identical states are recomputed repeatedly.

The memoization cache ensures every (city, remainingFuel) state is solved only once.

Large Coordinate Values

Coordinates may be as large as:

10^9

A naive solution might incorrectly attempt coordinate compression or grid traversal.

The implementation avoids this entirely. It only computes pairwise absolute distances directly:

abs(locations[i] - locations[j])

This keeps the algorithm efficient regardless of coordinate magnitude.