What is the brute force approach and complexity for Path with Maximum Probability?

Multiply along every link, both directions, until a full round changes nothing with time complexity O(N · E) and space complexity O(N).

What is the optimal approach and complexity for Path with Maximum Probability?

Pop the most likely route first; the first pop of the end node is the answer with optimal time complexity O((N + E) log N) and space complexity O(N + E).

How do you identify the pattern for Path with Maximum Probability?

Look for key signals in the prompt: "probability of success on each edge" indicates Chances multiply along a route, and each one is at most 1.; "maximum probability" indicates We want the largest product, so the heap must pop the largest first.; "undirected edges" indicates Each link works in both directions, so store it twice in the adjacency list..

Path with Maximum Probability

Medium·LeetCode #1514 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given n nodes numbered 0 to n − 1, and a list of undirected links. Link i joins the two nodes in edges[i] = [a, b], and it works with probability succProb[i].

A route works only if every link on it works, so its chance is the product of its links' chances. Find the route from start_node to end_node with the highest chance, and return that chance. If no route exists, return 0. An answer within 1e-5 of the true value is accepted.

Write double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) inside class Solution.

Input

n, the number of nodes. edges, the links. succProb, the chance of each link (same order as edges). start_node and end_node.

Output

The highest chance of a route from start_node to end_node, or 0 if there is none.

Example 1

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start_node = 0, end_node = 2

Output: 0.25

The route 0 → 1 → 2 has chance 0.5 × 0.5 = 0.25. The direct link has only 0.2.

Example 2

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start_node = 0, end_node = 2

Output: 0.3

Now the direct link (0.3) beats 0.5 × 0.5 = 0.25.

Example 3

Input: n = 3, edges = [[0,1]], succProb = [0.5], start_node = 0, end_node = 2

Output: 0

No route reaches node 2.

Constraints

• 2 ≤ n ≤ 10^4
• 0 ≤ start_node, end_node < n
• start_node ≠ end_node
• 0 ≤ a, b < n
• a ≠ b
• 0 ≤ succProb.length == edges.length ≤ 2 × 10^4
• 0 ≤ succProb[i] ≤ 1
• There is at most one edge between every two nodes.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“probability of success on each edge”

→ Chances multiply along a route, and each one is at most 1.

“maximum probability”

→ We want the largest product, so the heap must pop the largest first.

“undirected edges”

→ Each link works in both directions, so store it twice in the adjacency list.

Approach Complexity Ladder

Brute Force — rounds until nothing improvesO(N · E)O(N)

Multiply along every link, both directions, until a full round changes nothing

Optimal — max-heap DijkstraO((N + E) log N)O(N + E)

Pop the most likely route first; the first pop of the end node is the answer

Brute Force Intuition

Start with best[start] = 1 and 0 everywhere else. Go through every link in both directions: if best[a] × p > best[b], update best[b]. Repeat full rounds until one round changes nothing. Then return best[end].

Recognition rule for this sub-pattern:

Min-heap of (distance, node). Skip stale entries; relax neighbours.

Remember this · Shortest Paths (Weighted)

Trigger

Weighted edges, "minimum cost / time / effort", at most K stops, negative weights, all-pairs distances.

Think

Are edge weights non-negative (Dijkstra), limited by stops (Bellman-Ford), or do I need every pair (Floyd)?

Key question

What is a node's "distance", and when is it final?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Shortest Paths (Weighted) translate into production architectures and low-level memory mechanics.

LLD Architecture