Path with Maximum Probability in TypeScript: Best Product First

A route with fewer edges isn't automatically more likely to succeed. Two reliable connections can beat one unreliable shortcut. LeetCode's Path with Maximum Probability problem asks us to compare routes by the product of their edge probabilities and return the best product between two nodes.
The graph is undirected, and every edge probability lies between zero and one. Those two details shape the implementation: each input edge belongs in both adjacency lists, and extending a route can never increase its probability. That second property is what makes a greedy priority‑queue search possible.
I'll keep the most promising discovered route at the front of a max heap. This looks much like a shortest‑path implementation, but the starting value, comparison direction, and combination operation all change. Altering only the heap order would leave two thirds of the job unfinished.
Multiplication Changes the Starting State
The starting node has probability one. We have not traversed an edge yet, so multiplying by the first edge probability should leave that probability unchanged. Starting at zero would make every candidate zero forever, which is a particularly efficient way to find no useful routes.
Every other node starts at zero, meaning no positive‑probability route has been discovered. Moving across an edge multiplies the current route probability by that edge's probability. A candidate is worth keeping only if it exceeds the best value already recorded for its destination.
For example, an arrival with probability 0.8 followed by an edge with probability 0.5 gives 0.4. A direct route with probability 0.3 is worse, even though it uses fewer edges. The route score is a product, not a sum, average, or count.
Two arrivals at the same node can be compared without remembering their complete histories. If one has a larger product, multiplying both by the same non‑negative future edge probabilities cannot make the smaller arrival win. We can therefore keep one best score per node under this problem's model.
Use a Max Heap, with the Implementation Included
This queue accepts a priority comparison. Passing a > b makes the largest probability emerge first. It stores immutable arrival records; an improved route adds another record instead of editing an item already inside the heap.
type QueueItem = { node: number; score: number };
class PriorityQueue {
private readonly items: QueueItem[] = [];
constructor(private readonly better: (a: number, b: number) => boolean) {}
push = (item: QueueItem): void => {
this.items.push(item);
let child = this.items.length - 1;
while (child > 0) {
const parent = Math.floor((child - 1) / 2);
if (!this.better(this.items[child].score, this.items[parent].score)) break;
[this.items[child], this.items[parent]] = [this.items[parent], this.items[child]];
child = parent;
}
};
pop = (): QueueItem | undefined => {
if (this.items.length === 0) return undefined;
const first = this.items[0];
const last = this.items.pop()!;
if (this.items.length > 0) {
this.items[0] = last;
let parent = 0;
while (parent * 2 + 1 < this.items.length) {
let child = parent * 2 + 1;
if (child + 1 < this.items.length &&
this.better(this.items[child + 1].score, this.items[child].score)) child++;
if (!this.better(this.items[child].score, this.items[parent].score)) break;
[this.items[parent], this.items[child]] = [this.items[child], this.items[parent]];
parent = child;
}
}
return first;
};
}The heap is ordered locally between parents and children, not fully sorted. That is enough to expose the best item at its root. Pushing and popping each repair at most one root‑to‑leaf path, giving logarithmic heap work without sorting the whole frontier after every update.
The duplicate‑arrival approach needs a stale check in the search. A record can remain in the heap after a later route improves the node's best probability. Skipping that old record avoids expanding a route we already know is inferior.
Build Both Directions, Then Search
The edge list and probability list share indices. I pair them when building the adjacency lists so each neighbour record carries the probability used to reach it. The function assumes the well‑formed node numbers and probabilities guaranteed by the exercise.
const maxProbability = (
n: number,
edges: number[][],
succProb: number[],
start: number,
end: number,
): number => {
const neighbours: Array<Array<{ node: number; probability: number }>> =
Array.from({ length: n }, () => []);
edges.forEach(([a, b], index) => {
neighbours[a].push({ node: b, probability: succProb[index] });
neighbours[b].push({ node: a, probability: succProb[index] });
});
const best = Array<number>(n).fill(0);
best[start] = 1;
const queue = new PriorityQueue((a, b) => a > b);
queue.push({ node: start, score: 1 });
let current: QueueItem | undefined;
while ((current = queue.pop()) !== undefined) {
const { node, score } = current;
if (score < best[node]) continue;
if (node === end) return score;
for (const edge of neighbours[node]) {
const candidate = score * edge.probability;
if (candidate > best[edge.node]) {
best[edge.node] = candidate;
queue.push({ node: edge.node, score: candidate });
}
}
}
return 0;
};The destination can be returned when a fresh arrival is popped, not when it is first discovered. Returning during insertion would allow an early mediocre route to win before a better route has reached the front of the heap.
If the heap empties without a positive arrival at the destination, the function returns zero. That covers both a disconnected destination and one reachable only through zero‑probability routes. The requested numeric answer is zero in either case, so the implementation doesn't need to distinguish them.
A Route That Improves After Discovery
Take edges from zero to one with probability 0.7, from one to two with probability 0.8, and directly from zero to two with probability 0.4. Expanding the start discovers probabilities 0.7 for node one and 0.4 for node two.
The heap extracts node one first. Extending its route produces 0.56 for node two, improving the previous record. The heap now contains two arrivals for node two: 0.56 and 0.4. The larger fresh arrival is extracted first and gives the answer 0.56.
If the search were continuing to other nodes, the later 0.4 arrival would fail the stale check. Keeping it in the heap until then is harmless. Trying to remove every obsolete arrival immediately would require additional index bookkeeping inside the heap, which is unnecessary for this implementation.
A probability‑one cycle cannot improve a score, because multiplication by one leaves it unchanged and relaxation requires a strict increase. A cycle with any smaller positive factor decreases the product. These observations explain why endlessly revisiting a cycle is neither useful nor necessary.
Why Largest First Settles a Node
Every route extension multiplies by a number no greater than one, so its score can only stay the same or decrease. Suppose the largest fresh queue score is p, but a better undiscovered route to that node exists. Somewhere along that route is the first not‑yet‑processed node.
Its predecessor would have offered a candidate at least as large as the better route's final product. That candidate would have been extracted before p. The supposed better route cannot remain hidden behind a smaller priority, so a fresh extraction settles the node's best score.
The probability bounds are essential to that argument. If edge multipliers could exceed one, a route could become better after travelling further, and cycles might repeatedly amplify its score. That would be a different optimisation problem with a different proof.
Floating Point is Part of the Result
JavaScript stores these probabilities as floating‑point numbers, so decimal products need not be represented exactly. Tests should compare results with an appropriate tolerance rather than expecting every decimal calculation to equal its handwritten form bit for bit. The exercise itself allows a small absolute error.
I do not add an arbitrary epsilon to the relaxation comparison. Doing so can suppress real improvements and changes the algorithm's rule. Comparing the computed candidate directly keeps the implementation faithful to the represented values; tolerance belongs in the external answer check.
Very long paths with tiny factors can underflow towards zero. A logarithmic formulation can improve numerical range: for positive probabilities, minimising the sum of negative logarithms is equivalent to maximising the product. Zero‑probability edges need separate handling because their logarithm is not finite. I would choose that formulation if the numeric range required it, not merely to make the implementation look more mathematical.
The graph's multiplication rule also shouldn't be mistaken for a general reliability model. Real‑world failures can be correlated, and probabilities estimated from data may need a more careful model. Here the edge‑product definition is supplied by the problem, so the algorithm optimises exactly that quantity.
Verification and Cost
For small graphs, I enumerate simple paths independently and calculate their products. Considering simple paths is sufficient because removing a cycle whose factors are all at most one cannot worsen the product. This reference is exponential and deliberately limited to tiny graphs; it is useful for checking the heap solution, not replacing it on large inputs.
Tests include disconnected nodes, zero and one probabilities, competing direct and indirect routes, and a route improved after discovery. With V nodes and E edges, adjacency storage is O(V + E). The lazy heap can hold O(E) arrivals, so a general bound is O(V + E log(E + 1)) time and O(V + E) space.
My Network Delay Time walkthrough and stop‑limited flights article show nearby problems with different scoring or state. Here, the useful habit is to write down what extending a route does before selecting the queue. Starting at one, multiplying, and preferring larger scores belong together.