1514. Path with Maximum Probability LeetCode Solution

In this guide, you will get 1514. Path with Maximum Probability LeetCode Solution with the best time and space complexity. The solution to Path with Maximum Probability problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Path with Maximum Probability solution in C++
Path with Maximum Probability solution in Java
Path with Maximum Probability solution in Python
Additional Resources

1514. Path with Maximum Probability LeetCode Solution image

Problem Statement of Path with Maximum Probability

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.

Complexity Analysis

Time Complexity: O(|E|\log |E|)
Space Complexity: O(|V| + |E|)

1514. Path with Maximum Probability LeetCode Solution in C++

class Solution {
 public:
  double maxProbability(int n, vector<vector<int>>& edges,
                        vector<double>& succProb, int start, int end) {
    // {a: [(b, probability_ab)]}
    vector<vector<pair<int, double>>> graph(n);
    // (the probability to reach u, u)
    priority_queue<pair<double, int>> maxHeap;
    maxHeap.emplace(1.0, start);
    vector<bool> seen(n);

    for (int i = 0; i < edges.size(); ++i) {
      const int u = edges[i][0];
      const int v = edges[i][1];
      const double prob = succProb[i];
      graph[u].emplace_back(v, prob);
      graph[v].emplace_back(u, prob);
    }

    while (!maxHeap.empty()) {
      const auto [prob, u] = maxHeap.top();
      maxHeap.pop();
      if (u == end)
        return prob;
      if (seen[u])
        continue;
      seen[u] = true;
      for (const auto& [nextNode, edgeProb] : graph[u]) {
        if (seen[nextNode])
          continue;
        maxHeap.emplace(prob * edgeProb, nextNode);
      }
    }

    return 0;
  }
};
/* code provided by PROGIEZ */

1514. Path with Maximum Probability LeetCode Solution in Java

class Solution {
  public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    // {a: [(b, probability_ab)]}
    List<Pair<Integer, Double>>[] graph = new List[n];
    // (the probability to reach u, u)
    Queue<Pair<Double, Integer>> maxHeap =
        new PriorityQueue<>((a, b) -> Double.compare(b.getKey(), a.getKey())) {
          { offer(new Pair<>(1.0, start)); }
        };
    boolean[] seen = new boolean[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int i = 0; i < edges.length; ++i) {
      final int u = edges[i][0];
      final int v = edges[i][1];
      final double prob = succProb[i];
      graph[u].add(new Pair<>(v, prob));
      graph[v].add(new Pair<>(u, prob));
    }

    while (!maxHeap.isEmpty()) {
      final double prob = maxHeap.peek().getKey();
      final int u = maxHeap.poll().getValue();
      if (u == end)
        return prob;
      if (seen[u])
        continue;
      seen[u] = true;
      for (Pair<Integer, Double> node : graph[u]) {
        final int nextNode = node.getKey();
        final double edgeProb = node.getValue();
        if (seen[nextNode])
          continue;
        maxHeap.add(new Pair<>(prob * edgeProb, nextNode));
      }
    }

    return 0;
  }
}
// code provided by PROGIEZ

1514. Path with Maximum Probability LeetCode Solution in Python

class Solution:
  def maxProbability(
      self,
      n: int,
      edges: list[list[int]],
      succProb: list[float],
      start: int,
      end: int,
  ) -> float:
    graph = [[] for _ in range(n)]  # {a: [(b, probability_ab)]}
    maxHeap = [(-1.0, start)]   # (the probability to reach u, u)
    seen = [False] * n

    for i, ((u, v), prob) in enumerate(zip(edges, succProb)):
      graph[u].append((v, prob))
      graph[v].append((u, prob))

    while maxHeap:
      prob, u = heapq.heappop(maxHeap)
      prob *= -1
      if u == end:
        return prob
      if seen[u]:
        continue
      seen[u] = True
      for nextNode, edgeProb in graph[u]:
        if seen[nextNode]:
          continue
        heapq.heappush(maxHeap, (-prob * edgeProb, nextNode))

    return 0
 # code by PROGIEZ