Skip to main content
Talentd

Number of Ways to Arrive at Destination - Solution & Explanation

MediumDynamic ProgrammingGraphTopological SortShortest Path17 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 âžť 6

Example 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 <= 200
  • n - 1 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • 1 <= timei <= 109
  • ui != vi
  • There is at most one road connecting any two intersections.
  • You can reach any intersection from any other intersection.

Approach Overview

Problem Overview: Given n intersections and bidirectional roads with travel times, compute how many distinct ways you can reach node n-1 from node 0 using the minimum total time. The graph can contain multiple routes, but only paths with the shortest distance count. The result must be returned modulo 1e9 + 7.

Approach 1: Dijkstra's Algorithm with Path Counting (Time: O(E log V), Space: O(V + E))

This approach combines classic shortest path computation with dynamic counting of paths. Use an adjacency list and a min-heap priority queue to run Dijkstra from node 0. Maintain two arrays: dist[i] for the shortest distance to node i, and ways[i] for the number of shortest paths reaching that node. When relaxing an edge, update normally if a strictly shorter distance is found and copy the path count from the parent. If another path reaches the same node with the exact same shortest distance, add the parent’s path count instead of replacing it. This effectively layers a dynamic programming idea on top of Dijkstra. The priority queue ensures nodes are processed in increasing distance order, which guarantees correctness for weighted graphs with non‑negative edges.

Approach 2: Bellman-Ford Adaptation (Time: O(V * E), Space: O(V))

Another way to compute shortest paths is the Bellman-Ford relaxation process. Iterate over all edges up to V-1 times, updating distances similarly to standard Bellman-Ford. Alongside the distance array, track a ways[] array storing the number of shortest routes to each node. When a relaxation produces a smaller distance, copy the path count from the source node; when it produces the same distance, add the counts. This approach works even if the algorithm repeatedly revisits nodes because the relaxations converge toward the minimum distance. The drawback is performance: iterating over every edge for each pass makes it significantly slower than heap-based methods for dense graphs.

Recommended for interviews: The expected solution uses Dijkstra with path counting. Interviewers want to see that you recognize the problem as a weighted graph shortest-path problem and augment the algorithm to track the number of optimal routes. Starting from brute reasoning about shortest paths is fine, but implementing the heap-based solution demonstrates strong algorithmic intuition and efficient handling of weighted graphs.

Approach 1: Dijkstra's Algorithm with Path Counting

Description: This approach extends the classic Dijkstra's algorithm by integrating path counting. During the process of finding the shortest path using Dijkstra's algorithm, we will maintain an additional array to count the number of ways to reach each node in the graph in the shortest time.

Steps:

  1. Initialize a distance array to store shortest distances, setting all to infinity except the source, which is 0.
  2. Initialize a ways array to count ways to reach each node, setting all to 0 except the source, which is 1.
  3. Process each node using a priority queue, similar to Dijkstra's algorithm.
  4. Whenever a new shortest path to a node is found, update the distance and ways count for that node.
  5. Whenever another path is found with the same shortest distance, increment the ways count by the value from the parent node.
  6. Continue until all nodes are processed.

Considerations: Ensure counting is done modulo 109 + 7 to handle large numbers.

This Python function utilizes Dijkstra's algorithm via a min-heap (priority queue) to compute the shortest travel time. It adds functionality to track the number of shortest paths leading to each node. Each time a node is visited, if a shorter path is found, it updates; if equally short, it increments the path count using modular arithmetic.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O((N + E) log N), where N is the number of nodes and E is the number of edges.
Space Complexity: O(N + E) for the graph representation and additional arrays.

Try this approach in the editor →

Approach 2: Bellman-Ford Algorithm Adaptation

Description: An adaptation of the Bellman-Ford algorithm is possible here due to its suitability for graphs with non-negative weights, though less efficient, still valid for counting shortest paths under simple constraints.

Steps:

  1. Initialize distances with infinity and set the source distance to 0.
  2. Initialize a ways array, set ways from the source to 1.
  3. Relax all edges N-1 times: for every edge, update distance and path counts.
  4. For the nth RELAXATION, update only if equal distance to handle multiple shortest paths.
  5. Repeat updates for n-1 iterations to saturate shortest distances.

Note: Though not the most optimized under standard constraints as seen with Dijkstra's, exploring this aids learning.

The Java solution employs Bellman-Ford to establish shortest paths by iteratively relaxing all edges. Additional logic manages path counting upon equal length paths. Repeated edge checks across (n-1) rounds ensure comprehension of total optimal paths.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(N * E), given every edge relaxes across nodes.
Space Complexity: O(N) for maintaining distances and counts arrays.

Try this approach in the editor →

Approach 3: Naive Dijkstra Algorithm

We define the following arrays:

  • g represents the adjacency matrix of the graph. g[i][j] represents the shortest path length from point i to point j. Initially, all are infinity, while g[0][0] is 0. Then we traverse roads and update g[u][v] and g[v][u] to t.
  • dist[i] represents the shortest path length from the starting point to point i. Initially, all are infinity, while dist[0] is 0.
  • f[i] represents the number of shortest paths from the starting point to point i. Initially, all are 0, while f[0] is 1.
  • vis[i] represents whether point i has been visited. Initially, all are False.

Then, we use the naive Dijkstra algorithm to find the shortest path length from the starting point to the end point, and record the number of shortest paths for each point during the process.

Finally, we return f[n - 1]. Since the answer may be very large, we need to take the modulus of 10^9 + 7.

The time complexity is O(n^2), and the space complexity is O(n^2), where n is the number of points.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dijkstra's Algorithm with Path Counting

Time Complexity: O((N + E) log N), where N is the number of nodes and E is the number of edges.
Space Complexity: O(N + E) for the graph representation and additional arrays.

Bellman-Ford Algorithm Adaptation

Time Complexity: O(N * E), given every edge relaxes across nodes.
Space Complexity: O(N) for maintaining distances and counts arrays.

Naive Dijkstra Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dijkstra's Algorithm with Path CountingO(E log V)O(V + E)Best choice for weighted graphs with non-negative edges. Efficient and commonly expected in interviews.
Bellman-Ford AdaptationO(V * E)O(V)Useful when demonstrating relaxation-based shortest path logic or when negative edges are possible.

Video Solution

G-40. Number of Ways to Arrive at Destination • take U forward • 244,242 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Arrive at Destination easy or hard?
Number of Ways to Arrive at Destination is considered a medium difficulty problem. The challenge is recognizing that shortest path computation must be combined with counting the number of optimal routes. Familiarity with Dijkstra's algorithm makes the implementation straightforward.
Number of Ways to Arrive at Destination Python/Java solution
Most implementations use Dijkstra's algorithm with a priority queue. Python typically uses heapq, Java uses PriorityQueue, and C++ uses priority_queue. Each version maintains distance and ways arrays and updates them during edge relaxation.
How to solve Number of Ways to Arrive at Destination in O(E log V)?
Use Dijkstra's algorithm with a priority queue. Track the shortest distance to each node and the number of shortest paths reaching it. When relaxing edges, update both arrays: replace the path count if a shorter distance appears, or add to it if the same shortest distance is found.
What is the best approach for Number of Ways to Arrive at Destination?
The most efficient approach uses Dijkstra's algorithm combined with path counting. While computing shortest distances with a min-heap, maintain a ways array that stores how many shortest paths reach each node. When another path produces the same shortest distance, add the counts instead of replacing them. This runs in O(E log V) time and O(V + E) space.
Is Number of Ways to Arrive at Destination asked at Google/Amazon/Meta?
Graph shortest-path problems with path counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variations often test Dijkstra's algorithm, counting shortest paths, or dynamic programming on graphs. This problem is a common medium-level interview pattern.
What data structure is used in Number of Ways to Arrive at Destination?
The solution relies on an adjacency list to represent the graph and a min-heap priority queue for Dijkstra's algorithm. Additional arrays store shortest distances and the number of ways to reach each node. These structures allow efficient edge relaxation and path counting.
What is the time complexity of Number of Ways to Arrive at Destination?
The optimal solution using Dijkstra's algorithm runs in O(E log V) time due to heap operations while processing edges. Space complexity is O(V + E) for the adjacency list, distance array, and path count array. A Bellman-Ford adaptation would take O(V * E) time.

Ready to solve this problem?

Practice Number of Ways to Arrive at Destination with our built-in code editor and test cases.

Practice on FleetCode
Previous

All Paths From Source to Target

Next

Path with Maximum Probability