Number of Ways to Arrive at Destination Interview Question for Meta

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] = [u_i, v_i, time_i] means that there is a road between intersections u_i and v_i that takes time_i 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 10^9 + 7. For example:

Example 1: 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: 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.

Solve the problem efficiently.

import heapq

def count_paths(n: int, roads: list[list[int]]) -> int:
    """Counts the number of ways to travel from intersection 0 to n - 1 in the shortest amount of time."""
    graph = [[] for _ in range(n)]
    for u, v, time in roads:
        graph[u].append((v, time))
        graph[v].append((u, time))

    dist = [float('inf')] * n
    ways = [0] * n
    dist[0] = 0
    ways[0] = 1

    pq = [(0, 0)]  # (distance, node)
    
    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                ways[v] = ways[u]
                heapq.heappush(pq, (dist[v], v))
            elif dist[v] == dist[u] + weight:
                ways[v] = (ways[v] + ways[u]) % (10**9 + 7)

    return ways[n - 1]

# Example Usage
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]]
print(count_paths(n, roads))

n = 2
roads = [[1,0,10]]
print(count_paths(n, roads))

Explanation:

Build the Graph:
- Create an adjacency list graph to represent the roads between intersections. Each element graph[i] is a list of tuples (neighbor, time) representing the intersections reachable from intersection i and the time it takes to travel to them.
Initialize Distance and Ways Arrays:
- dist array stores the shortest distance from the starting intersection (0) to each intersection. Initialize all elements to infinity except dist[0], which is initialized to 0.
- ways array stores the number of ways to reach each intersection with the shortest distance. Initialize all elements to 0 except ways[0], which is initialized to 1 (since there is one way to reach the starting intersection from itself).
Priority Queue (Heap):
- Use a min-heap pq to keep track of the intersections to visit. The heap stores tuples (distance, node), where distance is the shortest distance from the starting intersection to the node, and node is the intersection number. The heap is initialized with (0, 0) representing the starting intersection with a distance of 0.
Dijkstra's Algorithm with Path Counting:
- While the priority queue is not empty:
  - Extract the intersection u with the smallest distance d from the heap.
  - If the extracted distance d is greater than the current shortest distance dist[u] to intersection u, it means we have already processed this intersection with a shorter distance, so we skip it.
  - Iterate through the neighbors v of intersection u:
    - If the distance to v can be shortened by going through u (i.e., dist[v] > dist[u] + weight, where weight is the time it takes to travel from u to v):
      - Update dist[v] to the new shorter distance dist[u] + weight.
      - Set the number of ways to reach v to the same as the number of ways to reach u (i.e., ways[v] = ways[u]).
      - Push (dist[v], v) onto the priority queue.
    - If the distance to v is equal to the distance through u (i.e., dist[v] == dist[u] + weight):
      - Increment the number of ways to reach v by the number of ways to reach u (i.e., ways[v] = (ways[v] + ways[u]) % (10**9 + 7)). This is because we have found another shortest path to v.
Return Result:
- After processing all intersections, the ways[n - 1] element will contain the number of ways to reach the destination intersection n - 1 with the shortest distance. Return this value.

Big(O) Runtime Analysis

Building the Graph: O(E), where E is the number of edges (roads).
Dijkstra's Algorithm: O((V + E) log V), where V is the number of vertices (intersections) and E is the number of edges. In the worst case, each vertex can be added to the priority queue, and each edge can cause the distance to a vertex in the queue to be updated, leading to a logarithmic heap operation.
Overall: O((V + E) log V). Since the problem states that n - 1 <= roads.length <= n * (n - 1) / 2, E can be O(V^2) in the worst case, but more commonly will be closer to O(V). Thus, the runtime is typically close to O(E log V).

Big(O) Space Usage Analysis

Graph: O(E) to store the adjacency list.
dist array: O(V) to store the shortest distances to each intersection.
ways array: O(V) to store the number of ways to reach each intersection.
Priority Queue: O(V) in the worst case, as it can contain all vertices if each vertex is enqueued at some point.
Overall: O(V + E).