We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Arrive at Destination

Number: 2090

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Meta

Problem Description

Given a weighted undirected graph with n intersections (nodes) labeled from 0 to n-1 and a list of roads connecting intersections with associated travel times, determine the number of distinct ways to travel from intersection 0 to intersection n-1 using the shortest possible total travel time. Return the final result modulo 10^9 + 7.

Key Insights

  • The problem requires computing the shortest distance from the source (0) to the destination (n-1) in a weighted graph.
  • Dijkstra’s algorithm is a natural choice due to non-negative edge weights.
  • While computing the shortest distances, maintain a count of how many ways each node can be reached using the minimum time.
  • Update the count when a new shorter path is found or when another path leading to the same shortest distance is discovered.
  • Always perform modulus operations to handle large numbers.

Space and Time Complexity

Time Complexity: O(E log V), where E is the number of roads and V is the number of intersections. Space Complexity: O(V + E), which accounts for the distance array, ways array, and graph representation.

Solution

We modify Dijkstra's algorithm to not only compute the shortest path but also track the number of ways to reach each intersection using shortest possible travel times. We use:

  • A graph represented as an adjacency list.
  • A distance array (or vector) initialized with infinity for all nodes except the starting node (set to 0).
  • A ways array to count the number of ways to achieve the recorded shortest distance.
  • A priority queue (or min-heap) to efficiently fetch the next node with the smallest temporary distance. During the relaxation step for each neighbor, if a shorter path is found, update both the distance and the ways count; if an equally short path is found, add the number of new ways to the count modulo 10^9 + 7.

Code Solutions

import heapq

def countPaths(n, roads):
    MOD = 10**9 + 7
    # Build the graph as an adjacency list
    graph = [[] for _ in range(n)]
    for u, v, time in roads:
        graph[u].append((v, time))
        graph[v].append((u, time))
    
    # Initialize distance and ways arrays
    dist = [float('inf')] * n
    ways = [0] * n
    dist[0] = 0
    ways[0] = 1
    
    # Min-heap: (distance, node)
    heap = [(0, 0)]
    
    # Modified Dijkstra's algorithm
    while heap:
        current_dist, u = heapq.heappop(heap)
        if current_dist > dist[u]:
            continue
        for v, time in graph[u]:
            next_dist = current_dist + time
            if next_dist < dist[v]:
                dist[v] = next_dist
                ways[v] = ways[u]
                heapq.heappush(heap, (next_dist, v))
            elif next_dist == dist[v]:
                ways[v] = (ways[v] + ways[u]) % MOD
    return ways[n - 1]
← Back to All Questions