Number of Ways to Arrive at Destination

Medium

Microsoft

0 views

Topics:

GraphsDynamic Programming

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⁹ + 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 <= u_i, v_i <= n - 1
1 <= time_i <= 10⁹
u_i!= v_i
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.

Number of Ways to Arrive at Destination

Medium

Microsoft

0 views

Topics:

GraphsDynamic Programming

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⁹ + 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 <= u_i, v_i <= n - 1
1 <= time_i <= 10⁹
u_i!= v_i
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of nodes *n* and edges *m* in the graph? Can *n* or *m* be zero?
What is the data type and range of the edge weights (the time it takes to travel between nodes)? Can they be floating-point numbers or negative?
If there are multiple shortest paths to the destination, should I count them all, or just return 1?
Is the graph directed or undirected? Is it guaranteed to be connected?
If there is no path from the starting node to the destination node, what value should I return?

Brute Force Solution

Approach

To find the number of ways to reach a destination, the brute force approach explores every possible path, one at a time. It essentially tries every combination of roads you can take to see if it leads to the destination.

Here's how the algorithm would work step-by-step:

Start at the beginning and imagine all the possible roads you could take from there.
For each of those roads, imagine all the roads you could take next.
Keep going like this, exploring every possible route, until you either reach the destination or get stuck.
If you reach the destination, count that as one way to get there.
If you get stuck, just ignore that path and try another one.
Repeat this process until you've explored absolutely every single possible route.
Finally, add up all the times you reached the destination to find the total number of ways to get there.

Code Implementation

def number_of_ways_brute_force(number_of_nodes, roads):    number_of_ways = 0
    def explore_paths(current_node):
        nonlocal number_of_ways
        # If we reach the destination, increment the count

        if current_node == number_of_nodes - 1:
            number_of_ways += 1
            return
        
        # Iterate through each road to explore possible paths

        for start_node, end_node, time_taken in roads:
            if start_node == current_node:
                explore_paths(end_node)

    explore_paths(0)

    return number_of_ways

Big(O) Analysis

Time Complexity

O(exponential) – The brute force approach explores every possible path in the graph. In the worst case, it might have to examine all permutations of nodes, especially if the graph is densely connected or contains cycles. This involves potentially visiting the same node multiple times through different paths. The number of possible paths can grow exponentially with the number of nodes n, making the time complexity O(exponential).

Space Complexity

O(V+E) – The brute force approach, as described, explores all possible paths using a recursive or iterative method, effectively performing a Depth-First Search (DFS) or Breadth-First Search (BFS). In the worst-case scenario, this requires maintaining a stack (in the case of DFS) or a queue (in the case of BFS) to keep track of the nodes to visit, where V is the number of vertices (locations) and E is the number of edges (roads). Additionally, a data structure might be needed to keep track of visited locations to avoid cycles, which could store up to V vertices. Thus, the auxiliary space used is proportional to V+E in the worst case.

Optimal Solution

Approach

This problem asks us to find the number of shortest paths from a starting point to a destination. The key is to keep track of the shortest distance to each location and the number of ways to reach that location with that shortest distance as we go.

Here's how the algorithm would work step-by-step:

Imagine building your route step-by-step, always choosing the quickest path possible.
Start at the beginning and figure out the fastest way to get to each place along the way.
As you find faster routes, update your knowledge of how long it takes to get to each place.
Crucially, also keep track of *how many* different ways you can arrive at a place using the fastest route.
If you find a new route to a place that's just as fast as your current fastest route, add the number of ways to get to the new route to your total number of ways to get to that location using the fastest route.
Continue this process until you reach your destination. The number of ways you reached the destination with the shortest time is your answer.

Code Implementation

import heapq

def number_of_ways_to_arrive_at_destination(number_of_nodes, roads):
    adjacency_list = [[] for _ in range(number_of_nodes)]
    for source, destination, time in roads:
        adjacency_list[source].append((destination, time))
        adjacency_list[destination].append((source, time))

    shortest_distances = [float('inf')] * number_of_nodes
    shortest_distances[0] = 0
    number_of_ways = [0] * number_of_nodes
    number_of_ways[0] = 1

    priority_queue = [(0, 0)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > shortest_distances[current_node]:
            continue

        for neighbor, time_to_neighbor in adjacency_list[current_node]:
            distance_to_neighbor = current_distance + time_to_neighbor

            # Found a shorter path to the neighbor.
            if distance_to_neighbor < shortest_distances[neighbor]:
                shortest_distances[neighbor] = distance_to_neighbor
                number_of_ways[neighbor] = number_of_ways[current_node]
                heapq.heappush(priority_queue, (distance_to_neighbor, neighbor))

            # Found a path with the same shortest distance.
            elif distance_to_neighbor == shortest_distances[neighbor]:
                # Update the number of ways by adding the ways from the current node.
                number_of_ways[neighbor] = (number_of_ways[neighbor] + number_of_ways[current_node]) % (10**9 + 7)

    # Returning the number of ways to reach the destination.
    return number_of_ways[number_of_nodes - 1]

Big(O) Analysis

Time Complexity

O(E log V) – The algorithm uses Dijkstra's algorithm, which in this case is implemented with a min-priority queue. The priority queue operations (insertion and extraction of the minimum element) take O(log V) time, where V is the number of vertices (nodes). In the worst case, we might process each edge (E) in the graph when updating the shortest distances to the nodes in the priority queue. Therefore, the dominant time complexity comes from processing each edge which leads to an overall time complexity of O(E log V).

Space Complexity

O(N) – The algorithm maintains a 'shortest distance' array and a 'number of ways' array, both indexed by the locations (or nodes) along the path. In the worst case, these arrays will need to store information for every location, so their size is proportional to N, where N represents the number of locations. Since the algorithm also potentially keeps track of visited locations, this can also take up to O(N) space. Therefore, the auxiliary space used is primarily determined by these arrays, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Input graph is empty (no nodes or edges)	Return 0 ways, as there's no path from start to destination.
Start and destination are the same node.	Return 1 way, as the starting point itself is considered a destination arrival.
Graph contains zero-weight edges.	Dijkstra's algorithm needs modification to handle zero-weight edges correctly, preventing infinite loops if present.
Graph contains multiple shortest paths with the same total weight.	The algorithm should correctly count all paths that have the minimum possible weight.
Large graph with many nodes and edges.	Ensure the chosen algorithm (Dijkstra's or similar) is optimized for large graphs to avoid exceeding time limits, potentially using a priority queue.
Integer overflow when calculating the number of paths or the shortest path weight.	Use a larger data type like long to store path counts and weights to prevent overflow.
No path exists between the start and destination nodes.	Return 0 ways, indicating no valid path was found.
Graph contains disconnected components with destination unreachable.	Return 0 ways as the destination is not reachable from the starting node.