Number of Ways to Arrive at Destination
MedPrompt
You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.
You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.
Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 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: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6Example 2:
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
Constraints:
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= ui, vi <= n - 11 <= timei <= 109ui != vi- There is at most one road connecting any two intersections.
- You can reach any intersection from any other intersection.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a dynamic programming technique, the Floyd-Warshall algorithm, to find the shortest paths between all pairs of intersections. We modify the standard algorithm to not only track the shortest distance but also the number of ways to achieve that shortest distance.
Algorithm
- Create two 2D arrays:
dist[n][n]to store the shortest time from intersectionitoj, andways[n][n]to store the number of shortest paths fromitoj. - Initialize
distwith a very large value for all pairs,0fordist[i][i], and the given road times for direct connections. - Initialize
wayswith0for all pairs,1forways[i][i], and1for direct connections. - Iterate through all possible intermediate intersections
kfrom0ton-1. - For each pair of intersections
(i, j), check if the path fromitojviak(dist[i][k] + dist[k][j]) is better. - If
dist[i][k] + dist[k][j] < dist[i][j]: A new, shorter path is found. Updatedist[i][j]and setways[i][j] = (ways[i][k] * ways[k][j]) % MOD. - If
dist[i][k] + dist[k][j] == dist[i][j]: An alternative path of the same shortest length is found. Updateways[i][j] = (ways[i][j] + ways[i][k] * ways[k][j]) % MOD. - After all iterations,
ways[0][n-1]contains the final answer.
Walkthrough
The core idea is to iteratively consider each intersection k as an intermediate point in paths between any two intersections i and j. We maintain two 2D arrays: dist[i][j] for the shortest time from i to j, and ways[i][j] for the count of such paths. We initialize these matrices based on direct roads. Then, for every possible intermediate node k, we check if going from i to j through k improves the path. If dist[i][k] + dist[k][j] gives a shorter path to j, we update dist[i][j] and set the number of ways to ways[i][k] * ways[k][j]. If it results in a path of the same length, we add ways[i][k] * ways[k][j] to the existing ways[i][j]. After checking all intermediate nodes, ways[0][n-1] will hold the required count.
class Solution { public int countPaths(int n, int[][] roads) { long MOD = 1_000_000_007; long[][] dist = new long[n][n]; long[][] ways = new long[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) { dist[i][j] = Long.MAX_VALUE / 2; // Use a large value to avoid overflow } } ways[i][i] = 1; } for (int[] road : roads) { int u = road[0]; int v = road[1]; int time = road[2]; dist[u][v] = time; dist[v][u] = time; ways[u][v] = 1; ways[v][u] = 1; } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; ways[i][j] = (ways[i][k] * ways[k][j]) % MOD; } else if (dist[i][k] + dist[k][j] == dist[i][j]) { ways[i][j] = (ways[i][j] + (ways[i][k] * ways[k][j]) % MOD) % MOD; } } } } return (int) ways[0][n - 1]; }}Complexity
Time
O(n^3) due to the three nested loops. This is feasible for the given constraint of n <= 200.
Space
O(n^2) to store the `dist` and `ways` matrices.
Trade-offs
Pros
Relatively straightforward to implement using nested loops.
The logic is self-contained and doesn't require complex data structures like priority queues.
Cons
Less efficient than Dijkstra's algorithm, especially for sparse graphs.
Calculates shortest paths between all pairs of nodes, which is more work than required for this problem (we only need 0 to n-1).
Solutions
Solution
class Solution {private static final long INF = Long.MAX_VALUE / 2;private static final int MOD = (int)1 e9 + 7;public int countPaths(int n, int[][] roads) { long[][] g = new long[n][n]; long[] dist = new long[n]; long[] w = new long[n]; boolean[] vis = new boolean[n]; for (int i = 0; i < n; ++i) { Arrays.fill(g[i], INF); Arrays.fill(dist, INF); } for (int[] r : roads) { int u = r[0], v = r[1], t = r[2]; g[u][v] = t; g[v][u] = t; } g[0][0] = 0; dist[0] = 0; w[0] = 1; for (int i = 0; i < n; ++i) { int t = -1; for (int j = 0; j < n; ++j) { if (!vis[j] && (t == -1 || dist[j] < dist[t])) { t = j; } } vis[t] = true; for (int j = 0; j < n; ++j) { if (j == t) { continue; } long ne = dist[t] + g[t][j]; if (dist[j] > ne) { dist[j] = ne; w[j] = w[t]; } else if (dist[j] == ne) { w[j] = (w[j] + w[t]) % MOD; } } } return (int)w[n - 1]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.