Number of Ways to Arrive at Destination

Medium
951.

Number of Ways to Arrive at Destination

Number of Ways to Arrive at Destination is a medium coding problem on dynamic programming, graph and shortest path, asked in Amazon, Google and Microsoft interviews.

A city has n intersections numbered 0 … n - 1 joined by bidirectional roads; roads[i] = [u, v, time] gives the time to drive that road.

You start at intersection 0 and want to reach intersection n - 1 in the shortest possible time. Return how many different routes achieve that time, modulo 10^9 + 7.

Example 1

Input
n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output
4
Explanation
Four different routes all take 7 minutes.

Example 2

Input
n = 2, roads = [[1,0,10]]
Output
1
Explanation
Only one road.

Example 3

Input
n = 3, roads = [[0,1,1],[1,2,1],[0,2,2]]
Output
2
Explanation
Two routes both take 2 minutes.

Constraints

  • 1 <= n <= 200
  • n - 1 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 3
  • 0 <= u, v <= n - 1
  • 1 <= time <= 1000
  • u != v
  • There is at most one road connecting any two intersections.
  • You can reach any intersection from any other intersection.
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} n
 * @param {number[][]} roads
 * @return {number}
 */
var countPaths = function(n, roads) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Ways to Arrive at Destination — Problem & Solution

Number of Ways to Arrive at Destination solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Ways to Arrive at Destination is a medium coding problem on dynamic programming, graph and shortest path, asked in Amazon, Google and Microsoft interviews.

Problem statement

A city has n intersections numbered 0 … n - 1 joined by bidirectional roads; roads[i] = [u, v, time] gives the time to drive that road.

You start at intersection 0 and want to reach intersection n - 1 in the shortest possible time. Return how many different routes achieve that time, modulo 10^9 + 7.

Example 1

Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: Four different routes all take 7 minutes.

Example 2

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: Only one road.

Example 3

Input: n = 3, roads = [[0,1,1],[1,2,1],[0,2,2]]
Output: 2
Explanation: Two routes both take 2 minutes.

Constraints

  • 1 <= n <= 200
  • n - 1 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 3
  • 0 <= u, v <= n - 1
  • 1 <= time <= 1000
  • u != v
  • There is at most one road connecting any two intersections.
  • You can reach any intersection from any other intersection.

Hints for Number of Ways to Arrive at Destination

  1. Hint 1

    Run Dijkstra's algorithm, but carry a second number alongside the distance.

  2. Hint 2

    When you find a strictly shorter route to a node, its count is replaced by the count of the node you came from.

  3. Hint 3

    When you find an equally short route, the counts are added.

How to solve Number of Ways to Arrive at Destination

Dijkstra's algorithm with path counting. Alongside dist[v], keep ways[v]: when relaxing an edge, a strictly better distance replaces the count, and an equal distance adds to it.

Approach

  1. Set dist[0] = 0 and ways[0] = 1; everything else is infinity with 0 ways.
  2. Repeatedly finalise the unfinished node with the smallest distance.
  3. Relaxing u → v: if dist[u] + t < dist[v], set dist[v] and ways[v] = ways[u]; if equal, add ways[u] into ways[v] modulo 10^9 + 7.
  4. Return ways[n - 1].

Why it works

Counting works because a node's distance is final when it is popped: since every road takes positive time, no later discovery can shorten it, so every contribution it makes afterwards is genuinely on a shortest route. Only ways needs the modulus — dist is a real time and must stay exact, or comparisons between routes would go wrong.

Complexity

  • Time — O(n² + m) with a plain Dijkstra
  • Space — O(n + m)

Pitfalls

  • Reducing dist under the modulus destroys the comparisons; only ways is reduced.
  • Equal-distance routes must add counts, not overwrite them.
  • Roads are bidirectional, so each one goes into both adjacency lists.

Reference solution

Python

from typing import List
import heapq

def countPaths(n: int, roads: List[List[int]]) -> int:
    MOD = 1000000007
    adj = [[] for _ in range(n)]
    for u, v, t in roads:
        adj[u].append((v, t))
        adj[v].append((u, t))
    BIG = float('inf')
    dist = [BIG] * n
    ways = [0] * n
    dist[0] = 0
    ways[0] = 1
    heap = [(0, 0)]
    done = [False] * n
    while heap:
        d, u = heapq.heappop(heap)
        if done[u]:
            continue
        done[u] = True
        for v, t in adj[u]:
            if done[v]:
                continue
            nd = d + t
            if nd < dist[v]:
                dist[v] = nd
                ways[v] = ways[u]
                heapq.heappush(heap, (nd, v))
            elif nd == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD
    return ways[n - 1]

Java

public static int countPaths(int n, int[][] roads) {
    final int MOD = 1000000007;
    final int BIG = 1000000000;
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] r : roads) {
        adj.get(r[0]).add(new int[] { r[1], r[2] });
        adj.get(r[1]).add(new int[] { r[0], r[2] });
    }
    int[] dist = new int[n];
    long[] ways = new long[n];
    boolean[] done = new boolean[n];
    Arrays.fill(dist, BIG);
    dist[0] = 0;
    ways[0] = 1;
    for (int it = 0; it < n; it++) {
        int u = -1, best = BIG;
        for (int i = 0; i < n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        for (int[] e : adj.get(u)) {
            int v = e[0], t = e[1];
            if (done[v]) continue;
            int nd = dist[u] + t;
            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
            } else if (nd == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return (int) ways[n - 1];
}

C++

int countPaths(int n, vector<vector<int>>& roads) {
    const long long MOD = 1000000007;
    const int BIG = 1000000000;
    vector<vector<pair<int,int>>> adj(n);
    for (auto& r : roads) {
        adj[r[0]].push_back({ r[1], r[2] });
        adj[r[1]].push_back({ r[0], r[2] });
    }
    vector<int> dist(n, BIG);
    vector<long long> ways(n, 0);
    vector<char> done(n, 0);
    dist[0] = 0;
    ways[0] = 1;
    for (int it = 0; it < n; it++) {
        int u = -1, best = BIG;
        for (int i = 0; i < n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = 1;
        for (auto& e : adj[u]) {
            int v = e.first, t = e.second;
            if (done[v]) continue;
            int nd = dist[u] + t;
            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
            } else if (nd == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return (int) ways[n - 1];
}

JavaScript

var countPaths = function(n, roads) {
    var MOD = 1000000007, BIG = 1000000000, i, k;
    var adj = [];
    for (i = 0; i < n; i++) adj.push([]);
    for (i = 0; i < roads.length; i++) {
        adj[roads[i][0]].push([roads[i][1], roads[i][2]]);
        adj[roads[i][1]].push([roads[i][0], roads[i][2]]);
    }
    var dist = [], ways = [], done = [];
    for (i = 0; i < n; i++) { dist.push(BIG); ways.push(0); done.push(false); }
    dist[0] = 0;
    ways[0] = 1;
    for (var it = 0; it < n; it++) {
        var u = -1, best = BIG;
        for (i = 0; i < n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        for (k = 0; k < adj[u].length; k++) {
            var v = adj[u][k][0], t = adj[u][k][1];
            if (done[v]) continue;
            var nd = dist[u] + t;
            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
            } else if (nd === dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return ways[n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Graph Data Structure