algoadvance

Leetcode 743. Network Delay Time

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 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:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Clarifying Questions

  1. Can the travel times be negative?
    • No, the travel times are all positive integers.
  2. Can there be multiple edges between the same pair of nodes?
    • No, assume no multiple edges between the same pair.
  3. Is the graph always connected?
    • No, it is possible for some nodes to be unreachable from the starting node k.

Strategy

  1. Graph Representation: Represent the graph using an adjacency list where each node points to a list of (target, weight) pairs.
  2. Dijkstra’s Algorithm: Use Dijkstra’s algorithm to find the shortest path from the starting node k to all other nodes.
    • Initialize a priority queue with the starting node and a list to keep track of the shortest distance to each node.
    • Use the priority queue to explore the shortest distance nodes first, updating the neighbors’ distances.
    • If all nodes are reachable, the maximum distance in the list will be the answer; if not, return -1.

Code

import java.util.*;

public class NetworkDelayTime {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Initialize the graph as an adjacency list
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] time : times) {
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        // Dijkstra's Algorithm
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{k, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int time = current[1];

            if (time > dist[node]) continue;

            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0];
                int travelTime = neighbor[1];
                int newDist = dist[node] + travelTime;
                if (newDist < dist[nextNode]) {
                    dist[nextNode] = newDist;
                    pq.offer(new int[]{nextNode, newDist});
                }
            }
        }

        int maxTime = Arrays.stream(dist).skip(1).max().getAsInt();
        return maxTime == Integer.MAX_VALUE ? -1 : maxTime;
    }

    public static void main(String[] args) {
        NetworkDelayTime solution = new NetworkDelayTime();
        int[][] times = \ use example from above
        int n = 4;
        int k = 2;
        System.out.println(solution.networkDelayTime(times, n, k)); // Output: 2
    }
}

Time Complexity

The overall time complexity is O((V + E) log V). This should perform efficiently given typical problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI