LeetCode 1976: Number of Ways to Arrive at Destination Solution

Master LeetCode problem 1976 (Number of Ways to Arrive at Destination), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1976. Number of Ways to Arrive at Destination

Medium

Dynamic Programming Graph Topological Sort Shortest Path

Problem Explanation

Explanation:

To solve this problem, we can use Dijkstra's algorithm to find the shortest path from intersection 0 to intersection n-1. We will also keep track of the number of ways to reach each intersection in the shortest time. We will use a priority queue to explore the intersections in order of their shortest time to reach from intersection 0.

Initialize an array dist to store the shortest time to reach each intersection and an array ways to store the number of ways to reach each intersection in the shortest time.
Initialize dist[0] = 0 and ways[0] = 1, and add intersection 0 to the priority queue.
Repeat the following steps while the priority queue is not empty:
- Pop the intersection with the shortest time currTime from the priority queue.
- For each road connected to the current intersection, update the shortest time and number of ways to reach the neighboring intersection if a shorter time is found. If the time is equal to the current shortest time, add the number of ways to the ways array.
- If the time to reach the neighboring intersection is updated, add the intersection to the priority queue.
Finally, return the number of ways to reach intersection n-1 in the shortest time modulo 10^9 + 7.

Time Complexity: O(N log N), where N is the number of intersections.
Space Complexity: O(N)

Solution Code

import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        long MOD = 1000000007;
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] road : roads) {
            int u = road[0], v = road[1], w = road[2];
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }
        
        long[] dist = new long[n];
        long[] ways = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        ways[0] = 1;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
        pq.offer(new int[]{0, 0});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currNode = curr[0];
            long currTime = curr[1];
            
            if (currTime > dist[currNode]) {
                continue;
            }
            
            for (int[] next : graph.get(currNode)) {
                int nextNode = next[0];
                long nextTime = currTime + next[1];
                
                if (nextTime < dist[nextNode]) {
                    dist[nextNode] = nextTime;
                    ways[nextNode] = ways[currNode];
                    pq.offer(new int[]{nextNode, (int) nextTime});
                } else if (nextTime == dist[nextNode]) {
                    ways[nextNode] = (ways[nextNode] + ways[currNode]) % MOD;
                }
            }
        }
        
        return (int) ways[n - 1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1976 (Number of Ways to Arrive at Destination)?

This page provides optimized solutions for LeetCode problem 1976 (Number of Ways to Arrive at Destination) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1976 (Number of Ways to Arrive at Destination)?

The time complexity for LeetCode 1976 (Number of Ways to Arrive at Destination) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1976 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1976 in Java, C++, or Python.

Back to LeetCode Solutions