Path with Maximum Probability

Med

#1396Time: O(n * E), where `n` is the number of nodes and `E` is the number of edges. The algorithm has a main loop that runs `n-1` times, and inside this loop, it iterates through all `E` edges.Space: O(n), where `n` is the number of nodes. This is for the `maxProb` array used to store the maximum probabilities to each node.2 companies

Algorithms

Shortest Path

Data structures

Array Heap (Priority Queue)Graph

Companies

tcs BlackRock

Prompt

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach adapts the Bellman-Ford algorithm, which is typically used for finding the shortest paths in a weighted graph, even with negative edge weights. Instead of minimizing the sum of edge weights, we modify it to maximize the product of probabilities. The Bellman-Ford algorithm works by iteratively "relaxing" edges. In our modification, a relaxation step involves checking if traversing an edge can lead to a path with a higher total probability to a node and updating it if so.

Algorithm

Initialize a double array maxProb of size n with all values as 0.0.
Set maxProb[start] = 1.0.
Repeat the following steps n-1 times:
- Create a flag hasUpdate and set it to false.
- Iterate through each edge (u, v) with probability p.
- If a more probable path to v is found via u (i.e., maxProb[u] * p > maxProb[v]), update maxProb[v] = maxProb[u] * p and set hasUpdate to true.
- Since the graph is undirected, do the same for the other direction: if maxProb[v] * p > maxProb[u], update maxProb[u] = maxProb[v] * p and set hasUpdate to true.
- If after a full iteration over all edges, hasUpdate is false, it means no probabilities were improved, and we can break the loop early.
After the loops complete, maxProb[end] contains the maximum probability. Return this value.

Walkthrough

We maintain an array, maxProb, of size n, where maxProb[i] stores the maximum probability of a path from the start node to node i. We initialize maxProb[start] to 1.0 and all other entries to 0.0, as we have a 100% chance of being at the start initially and zero chance of being anywhere else.

The algorithm then iterates n-1 times. In each iteration, it processes all E edges of the graph. For each edge (u, v) with success probability p, it updates the probability to reach v if the path through u (maxProb[u] * p) is better than the current known probability maxProb[v]. Since the graph is undirected, the same update is considered for u via v. This process is repeated n-1 times to guarantee that the maximum probabilities for paths of all possible lengths (up to n-1 edges) are found. After the iterations, maxProb[end] will hold the solution.

1class Solution {2    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {3        double[] maxProb = new double[n];4        maxProb[start] = 1.0;5 6        // Bellman-Ford requires n-1 iterations in the worst case.7        for (int i = 0; i < n - 1; i++) {8            boolean hasUpdate = false;9            for (int j = 0; j < edges.length; j++) {10                int u = edges[j][0];11                int v = edges[j][1];12                double prob = succProb[j];13 14                if (maxProb[u] * prob > maxProb[v]) {15                    maxProb[v] = maxProb[u] * prob;16                    hasUpdate = true;17                }18                if (maxProb[v] * prob > maxProb[u]) {19                    maxProb[u] = maxProb[v] * prob;20                    hasUpdate = true;21                }22            }23            // Optimization: if no updates in an iteration, we can stop early.24            if (!hasUpdate) {25                break;26            }27        }28 29        return maxProb[end];30    }31}

Complexity

Time

O(n * E), where `n` is the number of nodes and `E` is the number of edges. The algorithm has a main loop that runs `n-1` times, and inside this loop, it iterates through all `E` edges.

Space

O(n), where `n` is the number of nodes. This is for the `maxProb` array used to store the maximum probabilities to each node.

Trade-offs

Pros

Relatively simple to understand and implement without complex data structures like priority queues.
It can handle all types of graphs, including those that would have negative cycles in a standard shortest-path context (though not relevant here).

Cons

The time complexity of O(n * E) is generally too slow for graphs of the size specified in the constraints, and it will likely result in a 'Time Limit Exceeded' error.

This problem can be solved efficiently by adapting Dijkstra's algorithm. Standard Dijkstra's finds the shortest path by minimizing a sum of weights. Here, we need to maximize a product of probabilities. We can modify the algorithm to achieve this by using a max-priority queue instead of a min-priority queue. This greedy approach ensures that we always explore the path that is currently the most probable, which is guaranteed to find the optimal solution because all edge 'weights' (probabilities) are positive, analogous to non-negative weights in the standard algorithm.

An alternative but equivalent method is to transform the problem. Maximizing a product p1 * p2 * ... is the same as maximizing its logarithm log(p1) + log(p2) + .... This, in turn, is equivalent to minimizing the sum of negative logarithms (-log(p1)) + (-log(p2)) + .... Since probabilities are ≤ 1, their logs are ≤ 0, and their negative logs are ≥ 0. This transforms the problem into a standard shortest path problem with non-negative weights, solvable by the classic Dijkstra's algorithm. The implementation below uses the direct maximization approach for simplicity.

Algorithm

Build an adjacency list representation of the graph where adj[u] contains a list of pairs (v, p), representing an edge from u to v with probability p.
Initialize a double array maxProb of size n with all values as 0.0. Set maxProb[start] = 1.0.
Create a max-priority queue that stores pairs of (probability, node) and orders them by probability in descending order.
Add the starting pair (1.0, start) to the priority queue.
While the priority queue is not empty:
- Extract the pair (currentProb, currentNode) with the highest probability.
- If currentNode is the end node, we have found the optimal path, so return currentProb.
- If currentProb is less than maxProb[currentNode], it means we've found a better path to this node already, so we skip this (stale) entry.
- For each neighbor neighborNode of currentNode with edge probability edgeProb:
  - Calculate the probability of the path through currentNode: newProb = currentProb * edgeProb.
  - If newProb is greater than maxProb[neighborNode], we have found a better path. Update maxProb[neighborNode] = newProb and add the new pair (newProb, neighborNode) to the priority queue.
If the loop finishes and the end node has not been reached, it is unreachable. Return 0.0.

Walkthrough

The core of this approach is to use a max-priority queue to greedily explore the most promising paths. We start at the start node with a probability of 1.

First, we represent the graph using an adjacency list for efficient access to neighbors. Then, we initialize an array maxProb to keep track of the maximum probability to reach each node from start, setting maxProb[start] to 1 and all others to 0.

We push the starting node and its probability (1.0, start) into a max-priority queue. The algorithm proceeds by repeatedly extracting the node with the highest probability from the queue. For the extracted node, we examine all its neighbors. For each neighbor, we calculate the probability of reaching it via the current node. If this new probability is higher than the previously recorded maximum probability for that neighbor, we update the maxProb array and push the neighbor with its new, higher probability into the queue.

We also include a check to discard stale entries from the queue—if we pull a node from the queue whose probability is already lower than what's in our maxProb array, we ignore it. The algorithm terminates when we extract the end node from the queue, as the greedy nature of Dijkstra's ensures this is the highest probability path.

1import java.util.*;2 3class Solution {4    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {5        // Adjacency list: Map<Node, List<Pair<Neighbor, Probability>>>6        Map<Integer, List<double[]>> adj = new HashMap<>();7        for (int i = 0; i < edges.length; i++) {8            int u = edges[i][0];9            int v = edges[i][1];10            double prob = succProb[i];11            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new double[]{v, prob});12            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new double[]{u, prob});13        }14 15        double[] maxProb = new double[n];16        maxProb[start] = 1.0;17 18        // Max-priority queue: {probability, node}19        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));20        pq.offer(new double[]{1.0, (double)start});21 22        while (!pq.isEmpty()) {23            double[] current = pq.poll();24            double currentProb = current[0];25            int currentNode = (int)current[1];26 27            if (currentNode == end) {28                return currentProb;29            }30            31            if (currentProb < maxProb[currentNode]) {32                continue;33            }34 35            if (!adj.containsKey(currentNode)) {36                continue;37            }38 39            for (double[] neighbor : adj.get(currentNode)) {40                int neighborNode = (int)neighbor[0];41                double edgeProb = neighbor[1];42                double newProb = currentProb * edgeProb;43 44                if (newProb > maxProb[neighborNode]) {45                    maxProb[neighborNode] = newProb;46                    pq.offer(new double[]{newProb, (double)neighborNode});47                }48            }49        }50 51        return 0.0; // end is not reachable52    }53}

Complexity

Time

O(E log n), where `n` is the number of nodes and `E` is the number of edges. Building the adjacency list takes O(E). The main loop processes each node and edge once. Each priority queue operation (insertion and extraction) takes O(log n) time. In the worst case, we perform one extraction per node and one insertion per edge.

Space

O(n + E), where `n` is the number of nodes and `E` is the number of edges. This space is used for the adjacency list O(E), the `maxProb` array O(n), and the priority queue, which can hold up to O(n) nodes in the worst case.

Trade-offs

Pros

Highly efficient and the standard algorithm for this type of problem.
Guaranteed to find the optimal path because the problem structure (multiplying probabilities between 0 and 1) is analogous to summing non-negative weights.

Cons

Slightly more complex to implement than the Bellman-Ford approach due to the need for an adjacency list and a priority queue.

Solutions

Solution

1class Solution {2public3  double maxProbability(int n, int[][] edges, double[] succProb, int start,4                        int end) {5    List<Pair<Integer, Double>>[] g = new List[n];6    Arrays.setAll(g, k->new ArrayList<>());7    for (int i = 0; i < edges.length; ++i) {8      int a = edges[i][0], b = edges[i][1];9      double s = succProb[i];10      g[a].add(new Pair<>(b, s));11      g[b].add(new Pair<>(a, s));12    }13    PriorityQueue<Pair<Double, Integer>> q =14        new PriorityQueue<>(Comparator.comparingDouble(Pair : : getKey));15    double[] d = new double[n];16    d[start] = 1.0;17    q.offer(new Pair<>(-1.0, start));18    while (!q.isEmpty()) {19      Pair<Double, Integer> p = q.poll();20      double w = p.getKey();21      w *= -1;22      int u = p.getValue();23      for (Pair<Integer, Double> ne : g[u]) {24        int v = ne.getKey();25        double t = ne.getValue();26        if (d[v] < d[u] * t) {27          d[v] = d[u] * t;28          q.offer(new Pair<>(-d[v], v));29        }30      }31    }32    return d[end];33  }34}

1class Solution {2public:3  double maxProbability(int n, vector<vector<int>> &edges,4                        vector<double> &succProb, int start, int end) {5    vector<vector<pair<int, double>>> g(n);6    for (int i = 0; i < edges.size(); ++i) {7      int a = edges[i][0], b = edges[i][1];8      double s = succProb[i];9      g[a].push_back({b, s});10      g[b].push_back({a, s});11    }12    vector<double> d(n);13    d[start] = 1.0;14    queue<pair<double, int>> q;15    q.push({1.0, start});16    while (!q.empty()) {17      auto p = q.front();18      q.pop();19      double w = p.first;20      int u = p.second;21      if (d[u] > w)22        continue;23      for (auto &e : g[u]) {24        int v = e.first;25        double t = e.second;26        if (d[v] < d[u] * t) {27          d[v] = d[u] * t;28          q.push({d[v], v});29        }30      }31    }32    return d[end];33  }34};

1class Solution:2    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int, ) -> float: g = defaultdict(list) for (a, b), s in zip(edges, succProb): g[a]. append((b, s)) g[b]. append((a, s)) q = [(- 1, start)] d = [0] * n d[start] = 1 while q: w, u = heappop(q) w = - w if d[u] > w: continue for v, t in g[u]: if d[v] < d[u] * t: d[v] = d[u] * t heappush(q, (- d[v], v)) return d[end]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem