The O(n) Club: Network Delay Time, Java, and Your Shortcut to Dijkstra’s Fame

The O(n) Club: Network Delay Time, Java, and Your Shortcut to Dijkstra’s Fame

⚡ TL;DR

Picture a network where you yell “coffee’s ready!” down one-way hallways and hope everyone hears you before it gets cold. Each hallway has its own delay (just like office politics), and your goal: work out how long it takes before even the furthest node gets the memo. If they can’t, return -1 and hope nobody notices! Brute force means meltdown—trust Dijkstra. Here’s the “I woke up for this?” Java version:

// Graph = adjacency list, picking fastest next hop via heap. Enjoy!
public int networkDelayTime(int[][] times, int n, int k) {
    Map<integer list>> graph = new HashMap<>();
    for (int[] t : times)
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[]{0, k});
    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int time = cur[0], node = cur[1];
        if (time > dist[node]) continue;
        if (!graph.containsKey(node)) continue;
        for (int[] edge : graph.get(node)) {
            int nei = edge[0], wt = edge[1];
            if (dist[nei] > time + wt) {
                dist[nei] = time + wt;
                heap.offer(new int[]{dist[nei], nei});
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        max = Math.max(max, dist[i]);
    }
    return max;
}
</int></integer>

🧠 How Devs Usually Mess This Up

Classic faceplants include:

• Pretending it’s an all-pairs party. Stop acting like every node invites every other node to the dance—this is single-source. Only care about the one loudmouth spreading news.
• Forgetting it’s a one-way street. Direction matters; sending gossip never guarantees a reply. Don’t flip edges unless you like phantom bugs.
• Using BFS for everything. BFS is amazing—when you don’t care about travel time. Here, use BFS and watch it choose the wrong “quickest” every time there’s a shortcut with a bigger weight. Use Dijkstra or live in shame.

🔍 What’s Actually Going On

Imagine you’re running a relay across a very gossipy campus. Each runner passes the message down (with delays). Dijkstra’s algorithm is your over-caffeinated dispatcher, always picking whoever can deliver the memo next-fastest via a min-heap (a digital version of “next in line, please!”). You only track the first time every room gets the gossip—never update it unless you found a truly quicker way. Broadcasting is done when the last person finally gets the news, or if you find there’s a room behind a locked door (then, sorry, return -1 and cancel the fire drill).

🛠️ PseudoCode

• Build the adjacency list:
  

  for each [u, v, w] in times:
    graph[u].add([v, w])

  Every node points to its outgoing edges with weights. No two-way radios here.

• Set up shortest time tracker:
  

  int[] dist = new int[n+1];
  Arrays.fill(dist, INFINITY);
  dist[k] = 0;

  Keep track of best-known arrival times to each node—source starts at 0, others are left in limbo.

• Launch the min-heap:
  

  pq.offer([0, k])

  Always process the soonest-arrival node next. Those latecomers don’t get VIP status.

• While heap exists, process:
  • Pop min-time node
  • If a better time already found, skip
  • For neighbors: if new arrival is quicker, update and re-heap
• Final scan:
  • If any node still in limbo, return -1 (sorry, they’re unreachable)
  • Return the maximum arrival time found—slowest is the bottleneck

💻 The Code

import java.util.*;
 class Solution {
  public int networkDelayTime(int[][] times, int n, int k) {
    Map<integer list>> graph = new HashMap<>();
    for (int[] t : times)
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[]{0, k});
    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int time = cur[0], node = cur[1];
        if (time > dist[node]) continue;
        if (!graph.containsKey(node)) continue;
        for (int[] edge : graph.get(node)) {
            int nei = edge[0], wt = edge[1];
            if (dist[nei] > time + wt) {
                dist[nei] = time + wt;
                heap.offer(new int[]{dist[nei], nei});
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        max = Math.max(max, dist[i]);
    }
    return max;
  }
}
</int></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Graph might be split: If someone’s out of the signal loop, it’s game over for all—return -1.
• One-based indexing—read the fine print: Yes, this is 1-based. Read the docs twice so you only rage once.
• Directed only: Don’t hop backwards; the intern can’t moonwalk. Handle directed edges or you’ll get haunted by wrong answers.
• Java’s heap won’t magic away duplicates: Always compare times on retrieval or risk updating with outdated slowpokes.
• Performance: Handles sparse graphs beautifully (O(E log V)); won’t set your IDE on fire.

🧠 Interviewer Brain-Tattoo

“Dijkstra’s: Because BFS and weighted graphs go together like coffee and… orange juice. You CAN do it, but why would you?”