Path with Maximum Probability - Practice Coding Problems

Path with Maximum Probability - Problem

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.

Input & Output

Example 1 — Basic Graph

$ Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2

› Output: 0.25000

💡 Note: Two paths exist: 0→2 (probability 0.2) and 0→1→2 (probability 0.5×0.5=0.25). Maximum is 0.25.

Example 2 — No Direct Path

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

› Output: 0.30000

💡 Note: Two paths: 0→2 (probability 0.3) and 0→1→2 (probability 0.5×0.5=0.25). Maximum is 0.3.

Example 3 — No Path Available

$ Input: n = 4, edges = [[0,1],[2,3]], succProb = [0.5,0.5], start = 0, end = 3

› Output: 0.00000

💡 Note: Nodes 0 and 3 are in different connected components, so no path exists.

Constraints

2 ≤ n ≤ 10⁴
0 ≤ start, end < n
start ≠ end
0 ≤ edges.length ≤ 2 * 10⁴
edges[i].length == 2
0 ≤ a_i, b_i < n
a_i ≠ b_i
0 < succProb[i] ≤ 1

Visualization

Tap to expand

Understanding the Visualization

Graph Input

Undirected graph with edge success probabilities

Path Search

Find path that maximizes probability product

Result

Return maximum probability or 0 if no path exists

Key Takeaway

🎯 Key Insight: Use Dijkstra's algorithm but maximize probability instead of minimizing distance

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to use Dijkstra's algorithm but maximize probability instead of minimizing distance. Use a max-heap to always explore the most promising path first. Best approach is Dijkstra with Max-Heap: Time: O((V+E) log V), Space: O(V+E)

Common Approaches

Approach	Time	Space	Notes
✓ Dijkstra's Algorithm with Max-Heap	O((V + E) log V)	O(V + E)	Use modified Dijkstra's algorithm to find maximum probability path
DFS with Path Exploration	O(n!)	O(n)	Explore all paths using DFS and track maximum probability

Dijkstra's Algorithm with Max-Heap — Algorithm Steps

Build adjacency list from edges
Initialize max-heap with start node
Process nodes in order of highest probability
Update probabilities when better path found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with probability 1.0 at source

Process

Always pick node with highest probability

Update

Relax neighbors if better path found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct HeapNode {
    int node;
    double prob;
};

struct Heap {
    struct HeapNode* arr;
    int size;
    int capacity;
};

struct Edge {
    int node;
    double prob;
    struct Edge* next;
};

struct Edge* graph[1000];
double maxProb[1000];

double solution(int n, int edges[][2], double* succProb, int edgeCount, int start, int end) {
    // Initialize
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
        maxProb[i] = 0.0;
    }
    maxProb[start] = 1.0;
    
    // Build graph
    for (int i = 0; i < edgeCount; i++) {
        int a = edges[i][0], b = edges[i][1];
        
        struct Edge* edge1 = malloc(sizeof(struct Edge));
        edge1->node = b;
        edge1->prob = succProb[i];
        edge1->next = graph[a];
        graph[a] = edge1;
        
        struct Edge* edge2 = malloc(sizeof(struct Edge));
        edge2->node = a;
        edge2->prob = succProb[i];
        edge2->next = graph[b];
        graph[b] = edge2;
    }
    
    // Simple implementation without full heap
    int processed[1000] = {0};
    
    while (1) {
        int bestNode = -1;
        double bestProb = 0;
        
        for (int i = 0; i < n; i++) {
            if (!processed[i] && maxProb[i] > bestProb) {
                bestProb = maxProb[i];
                bestNode = i;
            }
        }
        
        if (bestNode == -1 || bestProb == 0) break;
        
        processed[bestNode] = 1;
        
        if (bestNode == end) return bestProb;
        
        struct Edge* edge = graph[bestNode];
        while (edge != NULL) {
            double newProb = bestProb * edge->prob;
            if (newProb > maxProb[edge->node]) {
                maxProb[edge->node] = newProb;
            }
            edge = edge->next;
        }
    }
    
    return 0.0;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int edges[100][2];
    double succProb[100];
    int edgeCount = 0;
    int start, end;
    
    scanf("%d %d", &start, &end);
    
    double result = solution(n, edges, succProb, edgeCount, start, end);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((V + E) log V)

Each edge relaxation takes O(log V) due to heap operations

⚡ Linearithmic

Space Complexity

O(V + E)

Adjacency list storage plus heap and distance array

✓ Linear Space

67.2K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dijkstra's Algorithm with Max-Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler