Introduction

In this blog post, we will explore how to solve the LeetCode problem "1514" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 Output: 0.25000 Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 0.5 = 0.25. Example 2: Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2 Output: 0.30000 Example 3: Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 Output: 0.00000 Explanation: There is no path between 0 and 2. Constraints: 2 <= n <= 10^4 0 <= start, end < n start != end 0 <= a, b < n a != b 0 <= succProb.length == edges.length <= 210^4 0 <= succProb[i] <= 1 There is at most one edge between every two nodes.

Explanation

Here's the solution:

• High-Level Approach:

  • Build an adjacency list representation of the graph, storing probabilities as edge weights.
  • Use a modified Dijkstra's algorithm to find the path with the maximum probability. Instead of minimizing distances, we maximize probabilities.
  • Employ a priority queue (heap) to efficiently explore nodes with higher probabilities first.

• Complexity:

  • Runtime: O(E log V), where E is the number of edges and V is the number of vertices (nodes).
  • Storage: O(V + E)

Code

    import heapq

def maxProbability(n: int, edges: list[list[int]], succProb: list[float], start: int, end: int) -> float:
    """
    Finds the path with the maximum probability of success to go from start to end.

    Args:
        n: The number of nodes.
        edges: The list of edges, where edges[i] = [a, b].
        succProb: The list of success probabilities for each edge.
        start: The starting node.
        end: The ending node.

    Returns:
        The maximum probability of success.
    """

    graph = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, succProb[i]))
        graph[v].append((u, succProb[i]))

    probabilities = [0.0] * n
    probabilities[start] = 1.0

    pq = [(-1.0, start)]  # Use a max-heap (negate probabilities)

    while pq:
        prob, node = heapq.heappop(pq)
        prob = -prob  # Revert the negation

        if prob < probabilities[node]:
            continue  # Already found a better path

        if node == end:
            return prob

        for neighbor, edge_prob in graph[node]:
            new_prob = prob * edge_prob
            if new_prob > probabilities[neighbor]:
                probabilities[neighbor] = new_prob
                heapq.heappush(pq, (-new_prob, neighbor))

    return 0.0  # No path found