Leetcode 1976 : Number of Ways to Arrive at Destination

Problem Statement

You are in a city with 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 there is at most one road between any two intersections.

You are given an integer n and a 2D integer array of 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.

Test Cases

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 <= 10^9
ui != vi
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.

Intuition

We need to find the shortest path from the 0th node to the (n - 1)th node. For this, we can make use of any of the Shortest Path finding algorithms and here Dijkstra is suitable.

While we do the Dijkstra, if we use some kind of tracking to find, by how many ways we reach a particular node, for that particular shorter distance, then that store data structure will give us the number of ways we are looking for the final (n - 1)th node.

Approach

• Build the graph from the edges array.

• Initialise a distance array and a dp array to track the distance and number of ways respectively.

• Do the Dijkstra algorithm starting from the 0th node.

• Whenever we see the distance of a node is shorter, update the distance array and copy over the dp value of the source node to the distance node.

• Otherwise, whenever we see the distance of the node is equal to the source node, add the ways we have seen so far.

• We need to consider overflow and do MOD operation accordingly.

Complexity

• Time complexity:

O(ElogV) for the Dijkstra

• Space complexity:

O(V) for distance array + O(V) for dp array + O(V) for minHeap + O(E + V) for the graph adjacency list.

Code

class Solution {

    private static final long MOD = (int)(1e9 + 7);

    public int countPaths(int n, int[][] roads) {
        if (roads == null || n == 0) {
            return 0;
        }
        List<List<Pair>> graph = buildGraph(roads, n);
        long [] distance = new long [n];
        long [] dp = new long [n];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[0] = 0;
        dp[0] = 1;
        findShortestPath(graph, distance, n, dp);
        return (int)(dp[n - 1] % MOD);
    }

    private void findShortestPath(List<List<Pair>> graph, long [] distance, int n, long [] dp) {
        PriorityQueue<Pair> minHeap = new PriorityQueue<>((p1, p2) -> Long.compare(p1.time, p2.time));
        minHeap.offer(new Pair(0, 0));
        while (!minHeap.isEmpty()) {
            Pair topPair = minHeap.poll();
            int currentNode = topPair.node;
            long currentTime = topPair.time;
            List<Pair> children = graph.get(currentNode);
            for (Pair child : children) {
                int childNode = child.node;
                long childTime = child.time;
                if (distance[childNode] > currentTime + childTime) {
                    distance[childNode] = currentTime + childTime;
                    dp[childNode] = dp[currentNode];
                    minHeap.offer(new Pair(childNode, distance[childNode]));
                }
                else {
                    if (distance[childNode] == currentTime + childTime) {
                        dp[childNode] = (dp[childNode] + dp[currentNode]) % MOD;
                    }
                }
            }
        }
    }

    private List<List<Pair>> buildGraph(int [][] roads, int n) {
        List<List<Pair>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int [] road : roads) {
            graph.get(road[0]).add(new Pair(road[1], road[2]));
            graph.get(road[1]).add(new Pair(road[0], road[2]));
        }
        return graph;
    }
}

class Pair {
    int node;
    long time;
    public Pair(int node, long time) {
        this.node = node;
        this.time = time;
    }
}