Network Delay Time

This medium LC question can be solved by using Djikstra algorithm. The goal is to find the individual distances of nodes from a given node. Then, the maximum distance will be the total network delay time.

The time complexity for this algorithm is O(NlogN + E), N = number of nodes and E = number of edges. The space complexity will be O(N) as well;

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // use djikstra
        // make an adjancecy map
        // use priority queue to process nodes starting from K
        // then start processing other neighbors
        int result = 0;
        final Map<Integer, List<int[]>> graph = new HashMap<>();
        for(int[] time : times){
                graph.put(time[0], new ArrayList<>());                
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        final PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        final Map<Integer, Integer> distMap = new HashMap<>();
        pq.add(new int[] {K, 0});
            int[] current = pq.poll();
            int d = current[1];
            int node = current[0];
            if(distMap.containsKey(node)) continue;
            distMap.put(node, d);
            // explore the neighbors
                final List<int[]> neighbors = graph.get(node);    
                for(int[] neighbor : neighbors){
                    int d2 = neighbor[1];
                    int n2 = neighbor[0];
                        pq.add(new int[]{n2, d + d2});
        if(distMap.size() != N) return -1;
        for(Map.Entry<Integer, Integer> entry: distMap.entrySet()){
            result = Math.max(result, entry.getValue());
        return result;

Runtime: 35 ms, faster than 33.55% of Java online submissions for Network Delay Time. Memory Usage: 61.7 MB, less than 7.14% of Java online submissions for Network Delay Time.

comments powered by Disqus