1514. Path with Maximum Probability (Medium)

Problem

You are given an undirected graph with n nodes. edges[i] = [a, b] with succProb[i] means the probability of success traveling from a to b (and vice versa). Find the path from start to end with the maximum probability of success. Return 0 if no path exists.

Example

n=3, edges [[0,1],[1,2],[0,2]], succProb [0.5,0.5,0.2], start=0, end=2 → 0.25
- Path 0->1->2 has probability 0.5 * 0.5 = 0.25
- Direct 0->2 has probability 0.2
- 0.25 > 0.2, so answer is 0.25

LeetCode 1514 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, Bellman-Ford style relaxation

Repeat relaxation until no updates occur. Works because probabilities are always in (0, 1], so multiplying never increases the value — no negative-cycle analog.

def max_probability(n, edges, succ_prob, start, end):
    prob = [0.0] * n                          # L1: O(V) init
    prob[start] = 1.0                         # L2: O(1) seed
    for _ in range(n - 1):                    # L3: at most V-1 rounds
        updated = False
        for i, (u, v) in enumerate(edges):    # L4: O(E) per round
            p = succ_prob[i]
            if prob[u] * p > prob[v]:         # L5: O(1) relax u->v
                prob[v] = prob[u] * p
                updated = True
            if prob[v] * p > prob[u]:         # L6: O(1) relax v->u (undirected)
                prob[u] = prob[v] * p
                updated = True
        if not updated:                       # L7: O(1) early exit
            break
    return prob[end]                          # L8: O(1)

function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
    const prob = new Array(n).fill(0.0);      // L1: O(V) init
    prob[start] = 1.0;                        // L2: O(1) seed
    for (let round = 0; round < n - 1; round++) {  // L3: at most V-1 rounds
        let updated = false;
        for (let i = 0; i < edges.length; i++) {   // L4: O(E) per round
            const [u, v] = edges[i];
            const p = succProb[i];
            if (prob[u] * p > prob[v]) {      // L5: O(1) relax u->v
                prob[v] = prob[u] * p;
                updated = true;
            }
            if (prob[v] * p > prob[u]) {      // L6: O(1) relax v->u (undirected)
                prob[u] = prob[v] * p;
                updated = true;
            }
        }
        if (!updated) break;                  // L7: O(1) early exit
    }
    return prob[end];                         // L8: O(1)
}

func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
    prob := make([]float64, n)                    // L1: O(V) init
    prob[start] = 1.0                             // L2: O(1) seed
    for round := 0; round < n-1; round++ {        // L3: at most V-1 rounds
        updated := false
        for i, e := range edges {                 // L4: O(E) per round
            u, v, p := e[0], e[1], succProb[i]
            if prob[u]*p > prob[v] {              // L5: O(1) relax u->v
                prob[v] = prob[u] * p; updated = true
            }
            if prob[v]*p > prob[u] {              // L6: O(1) relax v->u (undirected)
                prob[u] = prob[v] * p; updated = true
            }
        }
        if !updated { break }                     // L7: O(1) early exit
    }
    return prob[end]                              // L8: O(1)
}

final class Solution {
    func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
        var best = Array(repeating: 0.0, count: n); best[start] = 1.0
        if n > 1 { for _ in 0..<(n - 1) { var next = best, changed = false; for index in edges.indices { let u = edges[index][0], v = edges[index][1], chance = succProb[index]; if best[u] * chance > next[v] { next[v] = best[u] * chance; changed = true }; if best[v] * chance > next[u] { next[u] = best[v] * chance; changed = true } }; best = next; if !changed { break } } }
        return best[end]
    }
}

Where the time goes, line by line

Variables: V = n (nodes), E = number of edges.

Line	Per-call cost	Times executed	Contribution
L1-L2 (init)	$O(1)$	V	$O(V)$
L3 (outer rounds)	$O(1)$	up to V-1	$O(V)$
L4 (edge scan)	$O(1)$	*E (V-1)**	*$O(V E)$** ← dominates
L5/L6 (relax)	$O(1)$	up to 2E per round	$O(V * E)$
L7 (early exit)	$O(1)$	up to V-1	$O(V)$

With early exit this is fast in practice, but worst-case is $O(V * E)$ . For a dense graph that is $O(V^3)$ .

Complexity

Time: $O(V * E)$ , driven by L4 (edge scan per round).
Space: $O(V)$ .

Approach 2: Modified Dijkstra with max-heap (optimal)

Standard Dijkstra minimizes cost; here we maximize probability. Swap the min-heap for a max-heap by negating probabilities (Python’s heapq is a min-heap).

Key insight: probabilities are multiplied along a path, so the “best” path uses the product of edge probabilities. This is still monotone: adding more edges can only decrease or maintain probability, just as adding more edges (with positive weight) increases distance in standard Dijkstra.

import heapq
from collections import defaultdict

def max_probability(n, edges, succ_prob, start, end):
    graph = defaultdict(list)                      # L1: O(1) init
    for i, (u, v) in enumerate(edges):             # L2: O(E) build adjacency
        graph[u].append((v, succ_prob[i]))
        graph[v].append((u, succ_prob[i]))

    prob = [0.0] * n                               # L3: O(V) init probabilities
    prob[start] = 1.0                              # L4: O(1) seed
    # max-heap: negate probability so largest comes out first
    heap = [(-1.0, start)]                         # L5: O(1) seed heap

    while heap:                                    # L6: main loop
        neg_p, u = heapq.heappop(heap)             # L7: O(log V) pop best prob
        p = -neg_p
        if p < prob[u]:                            # L8: O(1) stale check
            continue
        if u == end:                               # L9: O(1) early exit
            return p
        for v, edge_p in graph[u]:                 # L10: O(deg(u)) neighbors
            new_p = p * edge_p                     # L11: O(1) path prob
            if new_p > prob[v]:                    # L12: O(1) improvement check
                prob[v] = new_p                    # L13: O(1) update
                heapq.heappush(heap, (-new_p, v))  # L14: O(log V) push

    return prob[end]                               # L15: O(1) result

function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
    const graph = new Map<number, [number, number][]>();
    for (let i = 0; i < n; i++) graph.set(i, []);
    for (let i = 0; i < edges.length; i++) {       // L2: O(E) build adjacency
        const [u, v] = edges[i];
        graph.get(u)!.push([v, succProb[i]]);
        graph.get(v)!.push([u, succProb[i]]);
    }

    const prob = new Array(n).fill(0.0);            // L3: O(V) init probabilities
    prob[start] = 1.0;                              // L4: O(1) seed
    // max-heap via negation: store [-prob, node]
    const heap = new MaxProbHeap();
    heap.push([-1.0, start]);                       // L5: O(1) seed heap

    while (heap.size > 0) {                         // L6: main loop
        const [negP, u] = heap.pop();               // L7: O(log V) pop best prob
        const p = -negP;
        if (p < prob[u]) continue;                  // L8: O(1) stale check
        if (u === end) return p;                    // L9: O(1) early exit
        for (const [v, edgeP] of graph.get(u)!) {  // L10: O(deg(u)) neighbors
            const newP = p * edgeP;                 // L11: O(1) path prob
            if (newP > prob[v]) {                   // L12: O(1) improvement check
                prob[v] = newP;                     // L13: O(1) update
                heap.push([-newP, v]);              // L14: O(log V) push
            }
        }
    }
    return prob[end];                               // L15: O(1) result
}

// See 1514-path-with-maximum-probability-approach2.go for the full runnable program.
// Core function uses container/heap with negated probability for max-heap behavior.
func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
    graph := make([][]struct{ v int; prob float64 }, n)
    for i, e := range edges {                           // L2: O(E) build adjacency
        u, v := e[0], e[1]
        graph[u] = append(graph[u], struct{ v int; prob float64 }{v, succProb[i]})
        graph[v] = append(graph[v], struct{ v int; prob float64 }{u, succProb[i]})
    }
    prob := make([]float64, n)
    prob[start] = 1.0                                   // L4: O(1) seed
    h := &MinHeap1514{{negP: -1.0, node: start}}
    heap.Init(h)                                        // L5: O(1) seed heap
    for h.Len() > 0 {                                   // L6: main loop
        item := heap.Pop(h).(Item1514)
        p, u := -item.negP, item.node                   // L7: O(log V) pop best prob
        if p < prob[u] { continue }                     // L8: O(1) stale check
        if u == end { return p }                        // L9: O(1) early exit
        for _, edge := range graph[u] {                 // L10: O(deg(u)) neighbors
            newP := p * edge.prob                       // L11: O(1) path prob
            if newP > prob[edge.v] {                    // L12: O(1) improvement check
                prob[edge.v] = newP                     // L13: O(1) update
                heap.Push(h, Item1514{negP: -newP, node: edge.v})  // L14: O(log V) push
            }
        }
    }
    return prob[end]                                    // L15: O(1) result
}

Where the time goes, line by line

Variables: V = n (nodes), E = number of edges.

Line	Per-call cost	Times executed	Contribution
L1-L2 (build graph)	$O(1)$	E	$O(E)$
L3-L5 (init)	$O(1)$	V	$O(V)$
L6 (loop)	$O(1)$	up to E	$O(E)$
L7 (heappop)	$O(log V)$	up to E	$O(E log V)$ ← dominates
L8/L9 (checks)	$O(1)$	up to E	$O(E)$
L10 (neighbors)	$O(1)$	E total	$O(E)$
L14 (heappush)	$O(log V)$	up to E	$O(E log V)$ ← dominates

Each edge can produce at most one push (L14). With at most E pushes and each costing $O(log V)$ (heap size bounded by V), total heap work is $O(E log V)$ .

Complexity

Time: $O((V + E)$ log V), driven by L7/L14 (heap operations).
Space: $O(V + E)$ for the adjacency list and heap.

Why negation works

Python’s heapq pops the smallest item. We want the largest probability first. Negating flips the ordering:

max-heap of probabilities  ==  min-heap of negated probabilities

heappush(heap, (-0.5, node))  ->  pops as (-0.5) before (-0.2)
                                   i.e., prob 0.5 before prob 0.2

Trace on example

Graph: 0-1 (0.5), 1-2 (0.5), 0-2 (0.2)
prob = [1.0, 0.0, 0.0]
heap = [(-1.0, 0)]

Pop (-1.0, 0), p=1.0:
  neighbor 1: new_p = 1.0*0.5 = 0.5 > 0.0 -> push (-0.5, 1), prob[1]=0.5
  neighbor 2: new_p = 1.0*0.2 = 0.2 > 0.0 -> push (-0.2, 2), prob[2]=0.2

Pop (-0.5, 1), p=0.5:
  neighbor 0: new_p = 0.5*0.5 = 0.25 < prob[0]=1.0 -> skip
  neighbor 2: new_p = 0.5*0.5 = 0.25 > prob[2]=0.2 -> push (-0.25, 2), prob[2]=0.25

Pop (-0.25, 2), p=0.25: u==end -> return 0.25

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
        var graph = Array(repeating: [(Int, Double)](), count: n)
        for index in edges.indices { let u = edges[index][0], v = edges[index][1], chance = succProb[index]; graph[u].append((v, chance)); graph[v].append((u, chance)) }
        var best = Array(repeating: 0.0, count: n); best[start] = 1.0
        var queue = BinaryHeap<(Double, Int)>(hasHigherPriority: { $0.0 > $1.0 }); queue.insert((1.0, start))
        while let (chance, node) = queue.removeRoot() { if node == end { return chance }; if chance < best[node] { continue }; for (neighbor, edgeChance) in graph[node] { let candidate = chance * edgeChance; if candidate > best[neighbor] { best[neighbor] = candidate; queue.insert((candidate, neighbor)) } } }
        return 0.0
    }
}

Summary

Approach	Time	Space	Notes
Bellman-Ford relaxation	$O(V * E)$	$O(V)$	Simple, handles all cases
Modified Dijkstra	$O((V+E)$ log V)	$O(V+E)$	Optimal for non-zero probabilities

The mapping from standard Dijkstra: min distance becomes max probability, sum of weights becomes product of probabilities, infinity becomes 0.0, 0 (source distance) becomes 1.0 (certainty at source).

Test cases

import heapq
from collections import defaultdict

def max_probability(n, edges, succ_prob, start, end):
    graph = defaultdict(list)
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, succ_prob[i]))
        graph[v].append((u, succ_prob[i]))
    prob = [0.0] * n
    prob[start] = 1.0
    heap = [(-1.0, start)]
    while heap:
        neg_p, u = heapq.heappop(heap)
        p = -neg_p
        if p < prob[u]:
            continue
        if u == end:
            return p
        for v, edge_p in graph[u]:
            new_p = p * edge_p
            if new_p > prob[v]:
                prob[v] = new_p
                heapq.heappush(heap, (-new_p, v))
    return prob[end]

def _run_tests():
    assert abs(max_probability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2) - 0.25) < 1e-5
    assert abs(max_probability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.3], 0, 2) - 0.3) < 1e-5
    assert max_probability(3, [[0,1]], [0.5], 0, 2) == 0.0
    assert abs(max_probability(2, [[0,1]], [0.9], 0, 1) - 0.9) < 1e-5
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses modified Dijkstra (Approach 2) with inline MaxProbHeap (min-heap on negated prob).
class MaxProbHeap {
    private data: [number, number][] = [];
    push(item: [number, number]): void {
        this.data.push(item);
        let i = this.data.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p][0] <= this.data[i][0]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
            i = p;
        }
    }
    pop(): [number, number] {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < this.data.length && this.data[l][0] < this.data[s][0]) s = l;
                if (r < this.data.length && this.data[r][0] < this.data[s][0]) s = r;
                if (s === i) break;
                [this.data[s], this.data[i]] = [this.data[i], this.data[s]];
                i = s;
            }
        }
        return top;
    }
    get size(): number { return this.data.length; }
}

function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
    const graph = new Map<number, [number, number][]>();
    for (let i = 0; i < n; i++) graph.set(i, []);
    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i];
        graph.get(u)!.push([v, succProb[i]]);
        graph.get(v)!.push([u, succProb[i]]);
    }
    const prob = new Array(n).fill(0.0);
    prob[start] = 1.0;
    const heap = new MaxProbHeap();
    heap.push([-1.0, start]);
    while (heap.size > 0) {
        const [negP, u] = heap.pop();
        const p = -negP;
        if (p < prob[u]) continue;
        if (u === end) return p;
        for (const [v, edgeP] of graph.get(u)!) {
            const newP = p * edgeP;
            if (newP > prob[v]) { prob[v] = newP; heap.push([-newP, v]); }
        }
    }
    return prob[end];
}

console.assert(Math.abs(maxProbability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2) - 0.25) < 1e-5);
console.assert(Math.abs(maxProbability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.3], 0, 2) - 0.3) < 1e-5);
console.assert(maxProbability(3, [[0,1]], [0.5], 0, 2) === 0.0);
console.assert(Math.abs(maxProbability(2, [[0,1]], [0.9], 0, 1) - 0.9) < 1e-5);
console.log("all tests pass");

Network Delay Time, canonical Dijkstra (minimize distance)
Swim in Rising Water, Dijkstra variant (minimize max edge)
Cheapest Flights Within K Stops, Bellman-Ford with constraint

Dijkstra, the priority queue shortest path pattern for non negative edge weights.
Shortest Paths, the frontier model for minimizing distance, cost, or probability through a graph.

1514. Path with Maximum Probability (Medium)

Problem

Try it yourself

Approach 1: Brute force, Bellman-Ford style relaxation

Approach 2: Modified Dijkstra with max-heap (optimal)

Why negation works

Trace on example

Summary

Test cases

Related topics

Related concepts