Number of Restricted Paths From First to Last Node

Hard
946.

Number of Restricted Paths From First to Last Node

Number of Restricted Paths From First to Last Node is a hard coding problem on dynamic programming, graph and heap, asked in Amazon, Google and Microsoft interviews.

An undirected weighted connected graph has n nodes numbered 1 … n, with edges[i] = [u, v, weight]. Let distanceToLastNode(x) be the shortest distance from node x to node n.

A path z1 → z2 → … → zk is restricted when distanceToLastNode(z1) > distanceToLastNode(z2) > … > distanceToLastNode(zk). Return the number of restricted paths from node 1 to node n, modulo 10^9 + 7.

Example 1

Input
n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output
3

Example 2

Input
n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output
1
Explanation
Only `1 → 3 → 7` keeps the distances strictly decreasing.

Example 3

Input
n = 2, edges = [[1,2,5]]
Output
1

Constraints

  • 1 <= n <= 1000
  • n - 1 <= edges.length <= 2 * 10^4
  • edges[i].length == 3
  • 1 <= u, v <= n
  • u != v
  • 1 <= weight <= 1000
  • There is at most one edge between any two nodes.
  • There is at least one path between every pair of nodes.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countRestrictedPaths = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Restricted Paths From First to Last Node Solution

Number of Restricted Paths From First to Last Node solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Restricted Paths From First to Last Node is a hard coding problem on dynamic programming, graph and heap, asked in Amazon, Google and Microsoft interviews.

Problem statement

An undirected weighted connected graph has n nodes numbered 1 … n, with edges[i] = [u, v, weight]. Let distanceToLastNode(x) be the shortest distance from node x to node n.

A path z1 → z2 → … → zk is restricted when distanceToLastNode(z1) > distanceToLastNode(z2) > … > distanceToLastNode(zk). Return the number of restricted paths from node 1 to node n, modulo 10^9 + 7.

Example 1

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3

Example 2

Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Only `1 → 3 → 7` keeps the distances strictly decreasing.

Example 3

Input: n = 2, edges = [[1,2,5]]
Output: 1

Constraints

  • 1 <= n <= 1000
  • n - 1 <= edges.length <= 2 * 10^4
  • edges[i].length == 3
  • 1 <= u, v <= n
  • u != v
  • 1 <= weight <= 1000
  • There is at most one edge between any two nodes.
  • There is at least one path between every pair of nodes.

Hints for Number of Restricted Paths From First to Last Node

  1. Hint 1

    First compute the shortest distance from every node to node n with one run of Dijkstra's algorithm.

  2. Hint 2

    The "strictly decreasing" rule makes the allowed moves a DAG, so paths can be counted by dynamic programming.

  3. Hint 3

    Process nodes in increasing order of their distance to n.

How to solve Number of Restricted Paths From First to Last Node

Run Dijkstra from node n to get every node's distance, then count paths with ways[u] = Σ ways[v] over neighbours v that are strictly closer to n. Processing nodes in increasing distance makes every ways[v] final before it is used.

Approach

  1. Dijkstra from node n gives dist[x] for all x.
  2. Set ways[n] = 1 — the empty path ending at n.
  3. Sort the nodes by dist ascending and sweep them.
  4. For node u, sum ways[v] over neighbours with dist[v] < dist[u], modulo 10^9 + 7.
  5. Return ways[1].

Why it works

The strict inequality is what makes counting possible at all: it forbids cycles, turning the allowed moves into a DAG whose topological order is exactly "sorted by distance". Ties in dist never create an edge, since a move needs a strict drop, so equal-distance nodes can be processed in any relative order.

Complexity

  • Time — O(n² + m) with a plain Dijkstra, or O(m log n) with a heap
  • Space — O(n + m)

Pitfalls

  • Dijkstra must run from node n, not from node 1.
  • ways[n] = 1 is the base case; forgetting it makes every answer 0.
  • Take the modulus while summing, not only at the end.

Reference solution

Python

from typing import List
import heapq

def countRestrictedPaths(n: int, edges: List[List[int]]) -> int:
    MOD = 1000000007
    adj = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    BIG = float('inf')
    dist = [BIG] * (n + 1)
    dist[n] = 0
    heap = [(0, n)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    ways = [0] * (n + 1)
    ways[n] = 1
    for u in sorted(range(1, n + 1), key=lambda x: dist[x]):
        if u == n:
            continue
        total = 0
        for v, _ in adj[u]:
            if dist[v] < dist[u]:
                total = (total + ways[v]) % MOD
        ways[u] = total
    return ways[1]

Java

public static int countRestrictedPaths(int n, int[][] edges) {
    final int MOD = 1000000007;
    final int BIG = 1000000000;
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[] { e[1], e[2] });
        adj.get(e[1]).add(new int[] { e[0], e[2] });
    }
    int[] dist = new int[n + 1];
    boolean[] done = new boolean[n + 1];
    Arrays.fill(dist, BIG);
    dist[n] = 0;
    for (int it = 0; it < n; it++) {
        int u = -1, best = BIG;
        for (int i = 1; i <= n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        for (int[] e : adj.get(u)) {
            if (dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];
        }
    }
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i + 1;
    final int[] d = dist;
    Arrays.sort(order, (a, b) -> d[a] - d[b]);
    long[] ways = new long[n + 1];
    ways[n] = 1;
    for (int node : order) {
        if (node == n) continue;
        long total = 0;
        for (int[] e : adj.get(node)) {
            if (dist[e[0]] < dist[node]) total = (total + ways[e[0]]) % MOD;
        }
        ways[node] = total;
    }
    return (int) ways[1];
}

C++

int countRestrictedPaths(int n, vector<vector<int>>& edges) {
    const long long MOD = 1000000007;
    const int BIG = 1000000000;
    vector<vector<pair<int,int>>> adj(n + 1);
    for (auto& e : edges) {
        adj[e[0]].push_back({ e[1], e[2] });
        adj[e[1]].push_back({ e[0], e[2] });
    }
    vector<int> dist(n + 1, BIG);
    vector<char> done(n + 1, 0);
    dist[n] = 0;
    for (int it = 0; it < n; it++) {
        int u = -1, best = BIG;
        for (int i = 1; i <= n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = 1;
        for (auto& p : adj[u]) {
            if (dist[u] + p.second < dist[p.first]) dist[p.first] = dist[u] + p.second;
        }
    }
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i + 1;
    sort(order.begin(), order.end(), [&](int a, int b) { return dist[a] < dist[b]; });
    vector<long long> ways(n + 1, 0);
    ways[n] = 1;
    for (int node : order) {
        if (node == n) continue;
        long long total = 0;
        for (auto& p : adj[node]) {
            if (dist[p.first] < dist[node]) total = (total + ways[p.first]) % MOD;
        }
        ways[node] = total;
    }
    return (int) ways[1];
}

JavaScript

var countRestrictedPaths = function(n, edges) {
    var MOD = 1000000007, BIG = 1000000000, i, k;
    var adj = [];
    for (i = 0; i <= n; i++) adj.push([]);
    for (i = 0; i < edges.length; i++) {
        adj[edges[i][0]].push([edges[i][1], edges[i][2]]);
        adj[edges[i][1]].push([edges[i][0], edges[i][2]]);
    }
    var dist = [], done = [];
    for (i = 0; i <= n; i++) { dist.push(BIG); done.push(false); }
    dist[n] = 0;
    for (var it = 0; it < n; it++) {
        var u = -1, best = BIG;
        for (i = 1; i <= n; i++) {
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        }
        if (u < 0) break;
        done[u] = true;
        for (k = 0; k < adj[u].length; k++) {
            var v = adj[u][k][0], w = adj[u][k][1];
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    var order = [];
    for (i = 1; i <= n; i++) order.push(i);
    order.sort(function(a, b) { return dist[a] - dist[b]; });
    var ways = [];
    for (i = 0; i <= n; i++) ways.push(0);
    ways[n] = 1;
    for (i = 0; i < order.length; i++) {
        var node = order[i];
        if (node === n) continue;
        var total = 0;
        for (k = 0; k < adj[node].length; k++) {
            var nb = adj[node][k][0];
            if (dist[nb] < dist[node]) total = (total + ways[nb]) % MOD;
        }
        ways[node] = total;
    }
    return ways[1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Graph Data Structure