#1514 Path with Maximum Probability

frequently reported atGoogle

the problem

In plain words

An undirected graph has n nodes. edges[i] = [a, b] succeeds with probability succProb[i]. Return the highest success probability of any path from start to end, or 0 if there is no path.

in n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2

out 0.25

0→1→2 = 0.5 × 0.5 = 0.25 beats 0→2 = 0.2.

in n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2

out 0.0

2 ≤ n ≤ 10⁴
0 ≤ edges.length ≤ 2·10⁴
0 ≤ succProb[i] ≤ 1
At most one edge between two nodes

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Multiplying by a number ≤ 1 can never increase a probability — the same way adding a weight ≥ 0 can never decrease a distance. That's exactly the condition Dijkstra needs, just with a max-heap and × instead of +.

solutions

From brute force to optimal

Repeat: for every edge (both directions) try prob[a] × p > prob[b]. Stop when nothing changes.

prob[start] = 1.
Up to n − 1 rounds over all edges, both directions.
Return prob[end].

timeO(n · E)

Up to n − 1 rounds × E edges; ~2·10⁸ in the worst case.

spaceO(n)

The prob array.

javajava.util.*

1class Solution {2    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {3        double[] prob = new double[n];                 // 0 = not reachable yet4        prob[start] = 1.0;5        for (int round = 1; round <= n - 1; round++) {6            boolean changed = false;7            for (int i = 0; i < edges.length; i++) {8                int a = edges[i][0], b = edges[i][1];9                double p = succProb[i];10                if (prob[a] * p > prob[b]) { prob[b] = prob[a] * p; changed = true; } // undirected:11                if (prob[b] * p > prob[a]) { prob[a] = prob[b] * p; changed = true; } // try both ways12            }13            if (!changed) break;14        }15        return prob[end];16    }17}

Always expand the most likely node; when end is polled, its probability is final.

Undirected adjacency list with probabilities.
Max-heap of {prob, node}; start {1.0, start}.
Poll; if it's end, return. Skip stale entries.
Relax: candidate = p × edgeProb; push if it beats prob[v].

timeO((n + E) log n)

Standard Dijkstra bound.

spaceO(n + E)

Adjacency list and heap.

javajava.util.*

1class Solution {2    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {3        List<List<double[]>> adj = new ArrayList<>();4        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());5        for (int i = 0; i < edges.length; i++) {6            adj.get(edges[i][0]).add(new double[] {edges[i][1], succProb[i]});7            adj.get(edges[i][1]).add(new double[] {edges[i][0], succProb[i]});8        }9        double[] prob = new double[n];10        prob[start] = 1.0;11        // Max-heap on probability: the most likely node is final when it is polled.12        PriorityQueue<double[]> pq = new PriorityQueue<>((x, y) -> Double.compare(y[0], x[0]));13        pq.offer(new double[] {1.0, start});14        while (!pq.isEmpty()) {15            double[] top = pq.poll();16            double p = top[0];17            int u = (int) top[1];18            if (u == end) return p;                    // first time end is polled = best19            if (p < prob[u]) continue;                 // stale entry20            for (double[] next : adj.get(u)) {21                int v = (int) next[0];22                double candidate = p * next[1];23                if (candidate > prob[v]) {24                    prob[v] = candidate;25                    pq.offer(new double[] {candidate, v});26                }27            }28        }29        return 0.0;                                    // end is unreachable30    }31}

in the room

How to say it in the interview

talk track

Say why Dijkstra is legal here: "multiplying by ≤ 1 is monotone, like adding ≥ 0."
Mention the log trick: maximise product ⇔ minimise Σ −log(p), all ≥ 0.

traps

Using a min-heap out of habit.
Forgetting the graph is undirected — add both directions.

what they ask next

Follow-ups

Could you turn it into a normal shortest path?

Yes: weight = −log(p) ≥ 0. Then the shortest path maximises the product. Doubles make the direct version simpler, though.

before you submit

Edge cases to test

No path from start to end → 0.0.
An edge with probability 0 is as good as no edge.
A longer path can win: 0.5 × 0.5 = 0.25 beats a direct 0.2.

practise next