1976. Number of Ways to Arrive at Destination

Number of Ways to Arrive at Destination (LeetCode 1976) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

How to solve Number of Ways to Arrive at Destination

Number of Ways to Arrive at Destination is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Work towards the solution in these steps:

1. First use any shortest path algorithm to get edges where dist[u] + weight = dist[v], here dist[x] is the shortest distance between node 0 and x
2. Using those edges only the graph turns into a dag now we just need to know the number of ways to get from node 0 to node n - 1 on a dag using dp

The reference solution runs in O((|E| + |V|) * log|V|) time and O(|E| + |V|) space.

The Number of Ways to Arrive at Destination solution and editorial walks through the full approach with reference code.

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.

Topics and companies

Topics: Dynamic Programming, Graph, Topological Sort, Shortest Path.

How to practise Number of Ways to Arrive at Destination on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((|E| + |V|) * log|V|) time and O(|E| + |V|) space.

Open Number of Ways to Arrive at Destination in the code editor, or read the Number of Ways to Arrive at Destination editorial for a worked solution with its approach and complexity analysis.

Where Number of Ways to Arrive at Destination sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Dijkstra's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Number of Ways to Arrive at Destination

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Find the Safest Path in a Grid — Medium, same subpattern
• Minimum Obstacle Removal to Reach Corner — Hard, same subpattern
• Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
• Minimum Weighted Subgraph With the Required Paths — Hard, same subpattern
• Network Delay Time — Medium, same subpattern
• Path with Maximum Probability — Medium, same subpattern

Number of Ways to Arrive at Destination FAQ