LeetCode 1514: Path with Maximum Probability Solution

Master LeetCode problem 1514 (Path with Maximum Probability), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1514. Path with Maximum Probability

Medium

Array Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the path with the maximum probability of success from the start node to the end node. We will keep track of the success probabilities for each node in the graph and update them as we explore different paths.

Create an adjacency list representation of the graph using the given edge list and success probabilities.
Initialize an array to store the success probability for each node, with the probability of the start node being 1.0 and all other nodes having a probability of 0.0.
Use a priority queue to explore nodes based on their success probabilities.
Start from the start node and explore neighboring nodes, updating their success probabilities with the maximum probability from the current node.
Continue exploring nodes until reaching the end node or until the priority queue is empty.
Return the success probability of the end node.

Time complexity: O(E log V), where E is the number of edges and V is the number of nodes. Space complexity: O(V) for storing the success probabilities and the priority queue.

Solution Code

import java.util.*;

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, List<double[]>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new double[]{edge[1], succProb[i]});
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new double[]{edge[0], succProb[i]});
        }

        double[] prob = new double[n];
        prob[start] = 1.0;

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Double.compare(prob[b], prob[a]));
        pq.offer(start);

        while (!pq.isEmpty()) {
            int node = pq.poll();
            if (node == end) {
                return prob[node];
            }
            if (!graph.containsKey(node)) {
                continue;
            }
            for (double[] next : graph.get(node)) {
                int neighbor = (int) next[0];
                double successProb = next[1];
                if (prob[node] * successProb > prob[neighbor]) {
                    prob[neighbor] = prob[node] * successProb;
                    pq.offer(neighbor);
                }
            }
        }

        return 0.0;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1514 (Path with Maximum Probability)?

This page provides optimized solutions for LeetCode problem 1514 (Path with Maximum Probability) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1514 (Path with Maximum Probability)?

The time complexity for LeetCode 1514 (Path with Maximum Probability) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1514 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1514 in Java, C++, or Python.

Back to LeetCode Solutions