solves network delay time in java

anishLearnsToCode · anishLearnsToCode · commit 2d6c5dac3d92 · 2022-05-09T18:25:24.000+02:00
diff --git a/README.md b/README.md
@@ -379,6 +379,7 @@
 | 724  | [Find Pivot Index](https://leetcode.com/problems/find-pivot-index)                                                                                        |                                    [![Java](assets/java.png)](src/FindPivotIndex.java) [![Python](assets/python.png)](python/find_pivot_index.py)                                    |                                                                                                                                   |
 | 728  | [Self Dividing Numbers](https://leetcode.com/problems/self-dividing-numbers)                                                                              |                               [![Java](assets/java.png)](src/SelfDividingNumbers.java) [![Python](assets/python.png)](python/self_dividing_number.py)                                |                                                                                                                                   |
 | 733  | [Flood Fill](https://leetcode.com/problems/flood-fill)                                                                                                    |                                         [![Java](assets/java.png)](src/FloodFill.java) [![Python](assets/python.png)](python/flood_fill.py)                                          |                                                                                                                                   |
+| 743  | [Network Delay Time](https://leetcode.com/problems/network-delay-time)                                                                                    |                                                                [![Java](assets/java.png)](src/NetworkDelayTime.java)                                                                 |                                                                                                                                   |
 | 734  | [Sentence Similarity](https://leetcode.com/problems/sentence-similarity)                                                                                  |                                                                                                                                                                                      |                                                                                                                                   |
 | 744  | [Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target)                                        |                 [![Java](assets/java.png)](src/FindSmallestLetterGreaterThanTarget.java) [![Python](assets/python.png)](python/find_smallest_letter_greater_than.py)                 |                                                                                                                                   |
 | 746  | [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs)                                                                        |                            [![Java](assets/java.png)](src/MinCostClimbingStairs.java) [![Python](assets/python.png)](python/min_cost_climbing_stairs.py)                             |                                                                                                                                   |
diff --git a/src/NetworkDelayTime.java b/src/NetworkDelayTime.java
@@ -0,0 +1,65 @@
+// https://leetcode.com/problems/network-delay-time
+// Single source shortest path algorithm (Dijkstra's Algorithm)
+// T: O(E log(N) for dijkstra + N for searching max val)
+// S: O(E + N)
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Queue;
+
+public class NetworkDelayTime {
+    private record Node(int value, long time) { }
+
+    public int networkDelayTime(int[][] times, int n, int k) {
+        final Map<Integer, Map<Integer, Integer>> graph = createDirectedGraphFrom(times);
+        final long[] minTimeTaken = getMinTimeTakenArray(n, k);
+        final Queue<Node> queue = new PriorityQueue<Node>(Comparator.comparing(Node::time));
+        queue.add(new Node(k, 0));
+
+        while (!queue.isEmpty()) {
+            Node node = queue.poll();
+            if (!graph.containsKey(node.value)) continue;
+            Map<Integer, Integer> vertexNode = graph.get(node.value);
+            for (int adjacent : vertexNode.keySet()) {
+                if (minTimeTaken[node.value - 1] + vertexNode.get(adjacent) < minTimeTaken[adjacent - 1]) {
+                    minTimeTaken[adjacent - 1] = minTimeTaken[node.value - 1] + vertexNode.get(adjacent);
+                    queue.add(new Node(adjacent, minTimeTaken[adjacent - 1]));
+                }
+            }
+        }
+
+        return allAreReached(minTimeTaken) ? (int) Arrays.stream(minTimeTaken).max().getAsLong() : -1;
+    }
+
+    private Map<Integer, Map<Integer, Integer>> createDirectedGraphFrom(int[][] times) {
+        final Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
+        for (int[] time : times) {
+            int start = time[0];
+            int destination = time[1];
+            int delay = time[2];
+
+            graph.putIfAbsent(start, new HashMap<>());
+            graph.get(start).put(destination, delay);
+        }
+        return graph;
+    }
+
+    private long[] getMinTimeTakenArray(int length, int start) {
+        long[] array = new long[length];
+        for (int i = 0 ; i < length ; i++) {
+            array[i] = Integer.MAX_VALUE;
+        }
+        array[start - 1] = 0;
+        return array;
+    }
+
+    private boolean allAreReached(long[] array) {
+        for (long val : array) {
+            if (val == Integer.MAX_VALUE) return false;
+        }
+        return true;
+    }
+}
