Introduction

In this blog post, we will explore how to solve the LeetCode problem "743" 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 a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. Example 1: Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 Example 2: Input: times = [[1,2,1]], n = 2, k = 1 Output: 1 Example 3: Input: times = [[1,2,1]], n = 2, k = 2 Output: -1 Constraints: 1 <= k <= n <= 100 1 <= times.length <= 6000 times[i].length == 3 1 <= ui, vi <= n ui != vi 0 <= wi <= 100 All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Explanation

Here's the breakdown of the solution:

• Dijkstra's Algorithm: We use Dijkstra's algorithm to find the shortest path from the source node k to all other nodes in the graph.
• Graph Representation: We represent the graph as an adjacency list, where each node stores a list of its neighbors and the corresponding travel times.

• Reachability Check: After running Dijkstra, we check if all nodes are reachable from the source. If any node has a distance of infinity, it means it's not reachable, and we return -1. Otherwise, we return the maximum distance among all reachable nodes, which represents the time it takes for the signal to reach all nodes.

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

• Storage Complexity: O(V + E)

Code

    import heapq

def networkDelayTime(times, n, k):
    """
    Finds the minimum time it takes for all nodes to receive a signal from node k.

    Args:
        times: A list of travel times as directed edges times[i] = (ui, vi, wi).
        n: The number of nodes in the network.
        k: The starting node.

    Returns:
        The minimum time it takes for all nodes to receive the signal.
        Returns -1 if it is impossible for all nodes to receive the signal.
    """

    # Build the graph as an adjacency list.
    graph = {}
    for u, v, w in times:
        if u not in graph:
            graph[u] = []
        graph[u].append((v, w))

    # Initialize distances to infinity for all nodes.
    distances = {i: float('inf') for i in range(1, n + 1)}
    distances[k] = 0  # Distance from source to itself is 0.

    # Use a priority queue (heap) to store nodes to visit based on their distance.
    pq = [(0, k)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)

        # If we've already found a shorter path to u, skip.
        if d > distances[u]:
            continue

        # Explore neighbors of u.
        if u in graph:
            for v, w in graph[u]:
                if distances[v] > distances[u] + w:
                    distances[v] = distances[u] + w
                    heapq.heappush(pq, (distances[v], v))

    # Check if all nodes are reachable.
    max_delay = 0
    for i in range(1, n + 1):
        if distances[i] == float('inf'):
            return -1
        max_delay = max(max_delay, distances[i])

    return max_delay