1575. Count All Possible Routes LeetCode Solution

In this guide, you will get 1575. Count All Possible Routes LeetCode Solution with the best time and space complexity. The solution to Count All Possible Routes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count All Possible Routes solution in C++
Count All Possible Routes solution in Java
Count All Possible Routes solution in Python
Additional Resources

1575. Count All Possible Routes LeetCode Solution image

Problem Statement of Count All Possible Routes

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.

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] <= 109
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

Complexity Analysis

Time Complexity: O(|\texttt{locations}|^2|\texttt{fuel}|)
Space Complexity: O(|\texttt{locations}||\texttt{fuel}|)

1575. Count All Possible Routes LeetCode Solution in C++

class Solution {
 public:
  int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
    vector<vector<int>> mem(locations.size(), vector<int>(fuel + 1, -1));
    return countRoutes(locations, start, finish, fuel, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of ways to reach the `finish` city from the i-th city
  // with `fuel` fuel.
  int countRoutes(const vector<int>& locations, int i, int finish, int fuel,
                  vector<vector<int>>& mem) {
    if (fuel < 0)
      return 0;
    if (mem[i][fuel] != -1)
      return mem[i][fuel];

    int res = i == finish ? 1 : 0;
    for (int j = 0; j < locations.size(); ++j) {
      if (j == i)
        continue;
      res += countRoutes(locations, j, finish,
                         fuel - abs(locations[i] - locations[j]), mem);
      res %= kMod;
    }

    return mem[i][fuel] = res;
  }
};
/* code provided by PROGIEZ */

1575. Count All Possible Routes LeetCode Solution in Java

class Solution {
  public int countRoutes(int[] locations, int start, int finish, int fuel) {
    Integer[][] mem = new Integer[locations.length][fuel + 1];
    return countRoutes(locations, start, finish, fuel, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of ways to reach the `finish` city from the i-th city
  // with `fuel` fuel.
  private int countRoutes(int[] locations, int i, int finish, int fuel, Integer[][] mem) {
    if (fuel < 0)
      return 0;
    if (mem[i][fuel] != null)
      return mem[i][fuel];

    int res = (i == finish) ? 1 : 0;
    for (int j = 0; j < locations.length; ++j) {
      if (j == i)
        continue;
      res += countRoutes(locations, j, finish, fuel - Math.abs(locations[i] - locations[j]), mem);
      res %= kMod;
    }

    return mem[i][fuel] = res;
  }
}
// code provided by PROGIEZ

1575. Count All Possible Routes LeetCode Solution in Python

class Solution:
  def countRoutes(
      self,
      locations: list[int],
      start: int,
      finish: int,
      fuel: int,
  ) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(i: int, fuel: int) -> int:
      """
      Returns the number of ways to reach the `finish` city from the i-th city
      with `fuel` fuel.
      """
      if fuel < 0:
        return 0

      res = 1 if i == finish else 0
      for j in range(len(locations)):
        if j == i:
          continue
        res += dp(j, fuel - abs(locations[i] - locations[j]))
        res %= kMod

      return res

    return dp(start, fuel)
 # code by PROGIEZ