Number of Ways to Arrive at Destination - Practice Coding Problems

Number of Ways to Arrive at Destination - Problem

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] = [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 10⁹ + 7.

Input & Output

Example 1 — Basic Graph

$ Input: n = 4, roads = [[0,1,1],[0,2,3],[1,3,2],[2,3,1]]

› Output: 1

💡 Note: There are two paths from 0 to 3: 0→1→3 (time 3) and 0→2→3 (time 4). Only one path has the shortest time of 3.

Example 2 — Multiple Shortest Paths

$ Input: n = 3, roads = [[0,1,1],[0,2,1],[1,2,1]]

› Output: 2

💡 Note: Two shortest paths from 0 to 2: direct path 0→2 (time 1) and path 0→1→2 (time 2). Wait, direct path is shorter, so answer is 1.

Example 3 — Single Path

$ Input: n = 2, roads = [[0,1,5]]

› Output: 1

💡 Note: Only one path from 0 to 1 with time 5, so count is 1.

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

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Weighted undirected graph with intersections and travel times

Find Shortest Paths

Use Dijkstra to find minimum time and count paths achieving it

Output Count

Return number of shortest paths modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Use Dijkstra's algorithm while tracking path counts - reset count on shorter path, add count on equal path

Asked in

G Google 15 f Facebook 12 a Amazon 8

Use Dijkstra's algorithm with path counting to find shortest paths while tracking the number of ways. The key insight is to modify Dijkstra to count paths: when finding a shorter path, reset count; when finding equal path, add to count. Time: O((V + E) log V), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(2^n)	O(n)	Try all possible paths from source to destination and count minimum time paths
Dijkstra with Path Counting	O((V + E) log V)	O(V + E)	Use Dijkstra's algorithm to find shortest paths while simultaneously counting the number of ways

Brute Force DFS — Algorithm Steps

DFS from source to find all paths
Track minimum time encountered
Count paths that match minimum time

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from intersection 0 with time 0

Explore Paths

Recursively try all neighbors, tracking current time

Count Minimum

Count paths that achieve minimum time to destination

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MOD 1000000007

typedef struct Edge {
    int to, time;
    struct Edge* next;
} Edge;

Edge* graph[1000];
int minTime = INT_MAX;
int count = 0;
int visited[1000];

void dfs(int node, int target, int currentTime, int n) {
    if (node == target) {
        if (currentTime < minTime) {
            minTime = currentTime;
            count = 1;
        } else if (currentTime == minTime) {
            count = (count + 1) % MOD;
        }
        return;
    }
    
    if (currentTime >= minTime) {
        return;
    }
    
    Edge* edge = graph[node];
    while (edge) {
        if (!visited[edge->to]) {
            visited[edge->to] = 1;
            dfs(edge->to, target, currentTime + edge->time, n);
            visited[edge->to] = 0;
        }
        edge = edge->next;
    }
}

int solution(int n, int roads[][3], int roadsSize) {
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < roadsSize; i++) {
        int u = roads[i][0], v = roads[i][1], time = roads[i][2];
        
        Edge* e1 = malloc(sizeof(Edge));
        e1->to = v;
        e1->time = time;
        e1->next = graph[u];
        graph[u] = e1;
        
        Edge* e2 = malloc(sizeof(Edge));
        e2->to = u;
        e2->time = time;
        e2->next = graph[v];
        graph[v] = e2;
    }
    
    minTime = INT_MAX;
    count = 0;
    visited[0] = 1;
    dfs(0, n - 1, 0, n);
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simplified parsing for this example
    int roads[100][3];
    int roadsSize = 0;
    
    int result = solution(n, roads, roadsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, explores all possible paths which can be exponential

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n intersections

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler