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.
- Difficulty: Medium
- Topics: Dynamic Programming, Graph, Shortest Path, Topological Sort
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= u, v <= n - 11 <= time <= 1000u != vThere 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
Hint 1
Run Dijkstra's algorithm, but carry a second number alongside the distance.
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.
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
- Set
dist[0] = 0andways[0] = 1; everything else is infinity with 0 ways. - Repeatedly finalise the unfinished node with the smallest distance.
- Relaxing
u → v: ifdist[u] + t < dist[v], setdist[v]andways[v] = ways[u]; if equal, addways[u]intoways[v]modulo10^9 + 7. - 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
distunder the modulus destroys the comparisons; onlywaysis 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