What is the time complexity of Path with Maximum Probability?

The optimal solution has a time complexity of O(E + NlogN).

What is the space complexity of Path with Maximum Probability?

The space complexity is O(N + E).

What data structures are used to solve Path with Maximum Probability?

This problem uses Array, Graph, Heap (Priority Queue), Shortest Path. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Path with Maximum Probability?

Insight 1: This problem is a variation of the shortest path problem. Instead of minimizing distance, we need to maximize probability. Since probabilities are multiplied along a path, we can adapt shortest path algorithms to find the path with maximum probability. Insight 2: Dijkstra's algorithm, typically used for shortest path problems, can be adapted here. Instead of minimizing the sum of edge weights, we maximize the product of edge probabilities. Using a priority queue (heap) is crucial for efficiently selecting the next node to explore.

Which companies ask LeetCode 1514. Path with Maximum Probability in interviews?

This problem is frequently asked at BlackRock, tcs.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Path with Maximum Probability - LeetCode 1514 Solution

Path with Maximum Probability - Complete Solution Guide

Path with Maximum Probability is LeetCode problem 1514, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 answe

Detailed Explanation

The problem asks us to find the path with the maximum probability of success between a starting node and an ending node in a weighted, undirected graph. The graph is represented by a list of edges, where each edge connects two nodes, and a corresponding list of success probabilities for traversing each edge. The goal is to return the maximum probability of reaching the end node from the start node, considering all possible paths. If no path exists, the function should return 0. The result should be accurate to within 1e-5.

Solution Approach

The provided solution uses a modified version of Dijkstra's algorithm to find the path with the maximum probability. The algorithm maintains an adjacency list representation of the graph, a priority queue to store nodes to visit based on their current maximum probability, and an array to track the maximum probability of reaching each node from the starting node. It iteratively explores the graph, updating the maximum probability of reaching each node and adding it to the priority queue if a better probability is found.

Step-by-Step Algorithm

Step 1: Create an adjacency list representation of the graph. For each edge (u, v) with probability p, add v to u's neighbor list with the associated probability, and add u to v's neighbor list with the same probability (since the graph is undirected).
Step 2: Initialize an array `max_probs` of size n, where `max_probs[i]` represents the maximum probability of reaching node i from the start node. Set `max_probs[start_node]` to 1.0 (the probability of being at the start node is 1). Initialize all other elements of `max_probs` to 0.0.
Step 3: Create a max-heap (priority queue) and insert the starting node with its probability (1.0). Store the probability as a negative value to simulate a max-heap using a min-heap implementation.
Step 4: While the priority queue is not empty:
a. Extract the node `u` with the highest probability (smallest negative probability) from the priority queue.
b. If the current probability of `u` is less than the stored `max_probs[u]`, it means we've already found a better path to `u`, so continue to the next iteration.
c. If `u` is the end node, return the current probability.
d. Iterate through the neighbors `v` of `u` in the adjacency list:
i. Calculate the new probability of reaching `v` by multiplying the current probability of `u` with the probability of the edge between `u` and `v`.
ii. If the new probability is greater than the current `max_probs[v]`, update `max_probs[v]` with the new probability and insert `v` into the priority queue with the negative of the new probability.
Step 5: If the end node is not reached after exploring all possible paths, it means there is no path from the start node to the end node. Return 0.0.

Key Insights

Insight 1: This problem is a variation of the shortest path problem. Instead of minimizing distance, we need to maximize probability. Since probabilities are multiplied along a path, we can adapt shortest path algorithms to find the path with maximum probability.
Insight 2: Dijkstra's algorithm, typically used for shortest path problems, can be adapted here. Instead of minimizing the sum of edge weights, we maximize the product of edge probabilities. Using a priority queue (heap) is crucial for efficiently selecting the next node to explore.
Insight 3: We need to use a max-heap (priority queue ordered by largest probability) to ensure that we always explore the path with the highest current probability first. Since standard priority queues are usually implemented as min-heaps, we can store negative probabilities to simulate a max-heap.

Complexity Analysis

Time Complexity: O(E + NlogN)

Space Complexity: O(N + E)

Topics

This problem involves: Array, Graph, Heap (Priority Queue), Shortest Path.

Companies

Asked at: BlackRock, tcs.

Path with Maximum Probability | LeetCode 1514

Medium

Array Graph Heap (Priority Queue)Shortest Path

Time: O(E + NlogN)Space: O(N + E)

Solution Code

Available in:

import java.util.*;

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        Map<Integer, List<Pair<Integer, Double>>> adj = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            double prob = succProb[i];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new Pair<>(v, prob));
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new Pair<>(u, prob));
        }

        double[] max_probs = new double[n];
        Arrays.fill(max_probs, 0.0);
        max_probs[start_node] = 1.0;

        PriorityQueue<Pair<Double, Integer>> pq = new PriorityQueue<>(Comparator.comparingDouble(Pair::getKey));
        pq.offer(new Pair<>(-1.0, start_node));

        while (!pq.isEmpty()) {
            Pair<Double, Integer> pair = pq.poll();
            double neg_prob = pair.getKey();
            int u = pair.getValue();
            double current_prob = -neg_prob;

            if (current_prob < max_probs[u]) {
                continue;
            }
            
            if (u == end_node) {
                return current_prob;
            }

            if (adj.containsKey(u)) {
                for (Pair<Integer, Double> neighbor : adj.get(u)) {
                    int v = neighbor.getKey();
                    double edge_prob = neighbor.getValue();
                    double new_prob = current_prob * edge_prob;
                    if (new_prob > max_probs[v]) {
                        max_probs[v] = new_prob;
                        pq.offer(new Pair<>(-new_prob, v));
                    }
                }
            }
        }

        return 0.0;
    }

    private static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1514: Path with Maximum Probability - Detailed explanation and solution approaches.

Topics

Array Graph Heap (Priority Queue)Shortest Path

Companies

BlackRocktcs

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:1514

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Create an adjacency list representation of the graph. For each edge (u, v) with probability p, add v to u's neighbor list with the associated probability, and add u to v's neighbor list with the same probability (since the graph is undirected).
2
Step 2: Initialize an array `max_probs` of size n, where `max_probs[i]` represents the maximum probability of reaching node i from the start node. Set `max_probs[start_node]` to 1.0 (the probability of being at the start node is 1). Initialize all other elements of `max_probs` to 0.0.
3
Step 3: Create a max-heap (priority queue) and insert the starting node with its probability (1.0). Store the probability as a negative value to simulate a max-heap using a min-heap implementation.
4
Step 4: While the priority queue is not empty:
5
a. Extract the node `u` with the highest probability (smallest negative probability) from the priority queue.
6
b. If the current probability of `u` is less than the stored `max_probs[u]`, it means we've already found a better path to `u`, so continue to the next iteration.
7
c. If `u` is the end node, return the current probability.
8
d. Iterate through the neighbors `v` of `u` in the adjacency list:
9
i. Calculate the new probability of reaching `v` by multiplying the current probability of `u` with the probability of the edge between `u` and `v`.
10
ii. If the new probability is greater than the current `max_probs[v]`, update `max_probs[v]` with the new probability and insert `v` into the priority queue with the negative of the new probability.
11
Step 5: If the end node is not reached after exploring all possible paths, it means there is no path from the start node to the end node. Return 0.0.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(E + NlogN)

💾

Space Complexity

O(N + E)

📝

Why?

The time complexity is dominated by the Dijkstra's algorithm part. The adjacency list construction is O(E). The priority queue operations (insert and extract-min) are O(logN) and can be executed at most N times. Exploring the neighbours is bounded by the number of edges E. The space complexity is due to the adjacency list to represent the graph (O(E)), the distance array (O(N)) and the priority queue (O(N)).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Bellman-Ford Algorithm

Bellman-Ford can also be used to solve this problem. However, Dijkstra's algorithm is generally more efficient for graphs without negative cycles.

Time: O(V*E), where V is the number of vertices and E is the number of edges.Space: O(V), where V is the number of vertices.

Trade-offs: Bellman-Ford is slower than Dijkstra's algorithm when there are no negative cycles, so Dijkstra's is preferred. Bellman-Ford can handle graphs with negative edge weights (or in this case, probabilities less than 1 if we take the negative logarithm of the probabilities), whereas Dijkstra's requires all edge weights to be non-negative (probabilities between 0 and 1).

✨

Key Insights

1Insight 1: This problem is a variation of the shortest path problem. Instead of minimizing distance, we need to maximize probability. Since probabilities are multiplied along a path, we can adapt shortest path algorithms to find the path with maximum probability.
2Insight 2: Dijkstra's algorithm, typically used for shortest path problems, can be adapted here. Instead of minimizing the sum of edge weights, we maximize the product of edge probabilities. Using a priority queue (heap) is crucial for efficiently selecting the next node to explore.
3Insight 3: We need to use a max-heap (priority queue ordered by largest probability) to ensure that we always explore the path with the highest current probability first. Since standard priority queues are usually implemented as min-heaps, we can store negative probabilities to simulate a max-heap.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: No path exists between the start and end nodes. The algorithm correctly returns 0.0 in this case because if the `end_node` is never reached during the Dijkstra's search, the function returns 0.0 outside of the while loop.
Edge case 2: The graph is disconnected. The algorithm will only explore the connected component containing the start node and return 0.0 if the end node is not in that component.
Edge case 3: Start and end nodes are the same. Since max_probs[start_node] is initialized to 1.0, and the algorithm directly returns current_prob if u == end_node, it will return 1.0 in this case, which is the correct probability.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using a min-heap instead of a max-heap. Since we want to maximize the probability, we need to prioritize exploring nodes with higher probabilities first.

✗Common mistake 2: Not handling the case where there is no path between the start and end nodes. The algorithm should return 0.0 in this case.

✗Common mistake 3: Incorrectly updating the `max_probs` array. The `max_probs` array should only be updated if the new probability is strictly greater than the current maximum probability for that node.

✗Common mistake 4: Not considering undirected edges. For each edge, remember to add it to the adjacency list for both nodes.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network routing. Finding the path with the highest reliability (probability of successful transmission) between two nodes in a network.

🏦Real-world scenario 2: Recommendation systems. Determining the path with the highest likelihood of a user clicking on a sequence of recommendations to reach a desired product.

🎮Real-world scenario 3: Financial modeling. Assessing the probability of success for a sequence of investments or trades.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I represent a graph in code?

Use adjacency list (HashMap or array of lists) for sparse graphs - it's space-efficient O(V+E). Use adjacency matrix for dense graphs or when you need O(1) edge lookup. For weighted graphs, store (neighbor, weight) pairs in adjacency lists.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Path with Maximum Probability"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether graph techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?