Network Delay Time (Dijkstra)

📋

Problem

Imagine you are managing a network of servers and want to know how long it takes for a signal to reach all servers starting from one source server.

You are given a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from u to v. There are n nodes labeled from 1 to n. Starting from node k, return the time it takes for all nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

1 ≤ n ≤ 10^51 ≤ times.length ≤ 10^5times[i].length == 31 ≤ u, v ≤ n1 ≤ w ≤ 100All edges are directed

Edge cases: No edges in times → output -1 (nodes unreachable)Single node network (n=1) → output 0 (signal already at node)Graph with cycles → algorithm must avoid infinite loops

</>

IDE

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:public int networkDelayTime(int[][] times, int n, int k)int networkDelayTime(vector<vector<int>>& times, int n, int k)function networkDelayTime(times, n, k)

def network_delay_time(times, n, k):
    # Write your solution here
    pass

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    // Write your solution here
    return 0;
}

function networkDelayTime(times, n, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: -1 when nodes are reachableIncorrectly marking reachable nodes as unreachable due to wrong distance initialization or update.✅ Initialize distances properly and update only when shorter path found; check max distance after processing.

Wrong: Too large value (e.g., 10 instead of 2)Greedy approach picking first edge without exploring all paths.✅ Implement full Dijkstra with priority queue and relax edges properly.

Wrong: 0 or wrong value for single nodeNot handling single node base case correctly.✅ Return 0 immediately if n=1.

Wrong: Infinite loop or stack overflowNot handling cycles properly in DFS or recursion.✅ Use priority queue and distance checks to avoid revisiting nodes unnecessarily.

Wrong: Timeout on large inputUsing brute force DFS or Bellman-Ford instead of efficient Dijkstra.✅ Use min-heap priority queue to achieve O(E log N) complexity.

✓

Test Cases

Focus on handling graphs with no edges and single node cases correctly.

Beware of greedy approaches and off-by-one errors in indexing.

Optimize your solution using a priority queue to handle large inputs efficiently.

t1_01basic

Input{"times":[[2,1,1],[2,3,1],[3,4,1]],"n":4,"k":2}

Expected2

⏱ Performance - must finish in 2000ms

Starting at node 2, signal reaches node 1 and 3 in 1 unit time, then node 4 in 2 units time.

💡 Think about shortest path from the start node to all others.

💡 Use Dijkstra's algorithm with a priority queue to find minimum travel times.

💡 Track the maximum shortest distance to any node; that is the answer.

Why it failed: Incorrect output means shortest path calculation is wrong; ensure you update distances only if new path is shorter and use a min-heap or priority queue.

✓ Correctly computed shortest paths and maximum delay.

t1_02basic

Input{"times":[[1,2,1],[2,3,2],[1,3,4]],"n":3,"k":1}

Expected3

⏱ Performance - must finish in 2000ms

Signal goes from 1 to 2 in 1 unit, then 2 to 3 in 2 units, total 3 units is shortest to node 3.

💡 Check all paths from the start node to each other node.

💡 Relax edges properly and update distances only if shorter.

💡 The longest shortest distance among all nodes is the result.

Why it failed: If output is not 3, likely not updating distances correctly or missing shorter path via node 2; fix edge relaxation logic.

✓ Correctly found shortest paths and maximum delay.

t2_01edge

Input{"times":[],"n":3,"k":1}

Expected-1

⏱ Performance - must finish in 2000ms

No edges means nodes 2 and 3 are unreachable from node 1, so return -1.

💡 Consider what happens if no edges exist in the graph.

💡 Check if all nodes are reachable from the start node.

💡 If any node is unreachable, return -1.

Why it failed: Returning a non -1 value means unreachable nodes not detected; ensure to check if max distance is infinity and return -1 accordingly.

✓ Correctly returns -1 when nodes are unreachable.

t2_02edge

Input{"times":[],"n":1,"k":1}

Expected0

⏱ Performance - must finish in 2000ms

Single node network means signal is already at node 1, so delay is 0.

💡 Consider the trivial case of a single node.

💡 Signal starts at node k, so delay to itself is zero.

💡 Return 0 if n=1 regardless of edges.

Why it failed: Returning non-zero means not handling single node base case; fix by returning 0 if n=1.

✓ Correctly returns 0 for single node network.

t2_03edge

Input{"times":[[1,2,1],[2,3,1],[3,1,1]],"n":3,"k":1}

Expected2

⏱ Performance - must finish in 2000ms

Graph has a cycle 1->2->3->1; shortest times are 0,1,2 respectively; algorithm must avoid infinite loops.

💡 Check how your algorithm handles cycles in the graph.

💡 Use a priority queue and update distances only if shorter to avoid infinite loops.

💡 Do not revisit nodes if no shorter path is found.

Why it failed: Infinite recursion or wrong output means cycles not handled; fix by using a priority queue and distance checks to prevent revisiting longer paths.

✓ Correctly handles cycles without infinite loops.

t3_01corner

Input{"times":[[1,2,1],[1,3,10],[2,3,1]],"n":3,"k":1}

Expected2

⏱ Performance - must finish in 2000ms

Greedy approach picking first edge 1->3 with weight 10 is wrong; shortest path is 1->2->3 with total 2.

💡 Beware of greedy approach that picks first edge without considering all paths.

💡 Use Dijkstra's algorithm to explore all possible paths and pick minimum.

💡 Update distances only if new path is shorter, not just first found.

Why it failed: Output 10 means greedy approach failed; fix by implementing full Dijkstra with priority queue and proper relaxation.

✓ Correctly avoids greedy trap and finds shortest path.

t3_02corner

Input{"times":[[1,2,1],[2,1,1],[2,3,2]],"n":3,"k":1}

Expected3

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded: edges are single use; algorithm must not assume multiple traversals to reduce cost.

💡 Edges represent single travel times, not unlimited usage.

💡 Do not assume repeated edge usage to reduce distance.

💡 Use standard shortest path logic without cycles reducing cost.

Why it failed: Output less than 3 means algorithm incorrectly assumes multiple edge uses; fix by treating edges as single-use directed edges.

✓ Correctly respects single-use edges and computes shortest path.

t3_03corner

Input{"times":[[1,2,1],[2,3,2],[3,4,3],[4,5,4],[5,6,5]],"n":6,"k":1}

Expected15

⏱ Performance - must finish in 2000ms

Off-by-one errors in indexing or distance updates can cause wrong max delay; correct max delay is sum of weights along path.

💡 Check indexing carefully when updating distances.

💡 Ensure distances array is 1-based or properly aligned with node labels.

💡 Max delay is max distance among all nodes reachable from k.

Why it failed: Output less than 15 means off-by-one or incorrect max distance calculation; fix indexing and max distance logic.

✓ Correctly computes max delay with proper indexing.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Test with n=100000 nodes and up to 100000 edges; O(E log N) Dijkstra must complete within 2 seconds.

💡 Use a priority queue (min-heap) to achieve O(E log N) complexity.

💡 Avoid repeated unnecessary relaxations and use adjacency list.

💡 Brute force DFS or Bellman-Ford will time out on this input.

Why it failed: TLE indicates algorithm is not O(E log N); fix by implementing Dijkstra with min-heap priority queue.

✓ Algorithm runs within time limit using efficient Dijkstra implementation.

Practice

1. You are given a list of courses and their prerequisite pairs. You need to determine if it is possible to finish all courses without running into a circular dependency. Which algorithmic approach guarantees an optimal solution to detect such cycles in the course dependency graph?

easy

A. Perform a topological sort using Kahn's Algorithm (BFS) to detect cycles by checking if all nodes can be processed.

B. Use a brute force approach that tries all possible course orders to find a valid sequence.

C. Apply dynamic programming to count the number of ways to complete courses without cycles.

D. Use a greedy algorithm that always picks the course with the fewest prerequisites first.

Solution

1. Step 1: Understand the problem as cycle detection in a directed graph

   The problem requires detecting if a cycle exists in the course prerequisite graph, which invalidates any course order.

2. Step 2: Identify the algorithm that detects cycles efficiently

   Kahn's Algorithm performs a topological sort using BFS and in-degree counts. If all nodes are processed, no cycle exists; otherwise, a cycle is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Topological sort with BFS is the standard cycle detection method for this problem [OK]

Hint: Topological sort detects cycles by processing all nodes [OK]

Common Mistakes:

• Greedy approach fails on complex dependencies
• Dynamic programming is not suited for cycle detection
• Brute force is inefficient and impractical

2. Consider the following code snippet that finds the smallest set of vertices to reach all nodes in a DAG. Given n = 4 and edges = [[0,1],[1,2],[2,3]], what is the final returned list?

easy

A. [0]

B. [3]

C. [0, 1]

D. [1]

Solution

1. Step 1: Initialize in-degree and queue

   Nodes: 0,1,2,3; in-degree: [0,1,1,1]. Only node 0 has zero in-degree, so queue = [0], result = [0].

2. Step 2: Process queue

   Pop 0, decrement in-degree of 1 to 0, enqueue 1. Pop 1, decrement in-degree of 2 to 0, enqueue 2. Pop 2, decrement in-degree of 3 to 0, enqueue 3. Pop 3, no neighbors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only node 0 has zero in-degree initially, so result is [0] [OK]

Hint: Only nodes with zero in-degree initially are in the result [OK]

Common Mistakes:

• Returning nodes that become zero in-degree later
• Returning all nodes visited in BFS
• Confusing final queue state with result

3. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

4. What is the time complexity of the Union-Find based algorithm to check if a graph with V vertices and E edges is bipartite?

medium

A. O(V^2) because each union operation can take linear time

B. O(V + E log V) due to sorting edges before union

C. O((V + E) α(V)) where α is the inverse Ackermann function

D. O(V + E) because union-find operations are constant time

Solution

1. Step 1: Identify number of union-find operations

   Each edge triggers at most one union operation, so total operations are O(E).

2. Step 2: Analyze union-find operation complexity

   Union-Find with path compression and union by rank has amortized time O(α(V)) per operation, where α is inverse Ackermann function.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-Find complexity is near-linear, not quadratic or logarithmic [OK]

Hint: Union-Find operations are almost constant time amortized [OK]

Common Mistakes:

• Assuming union is linear time
• Confusing sorting necessity
• Ignoring inverse Ackermann function

5. Suppose the problem is modified so that islands can be connected diagonally as well (8-direction connectivity). Which of the following changes to the DFS approach correctly counts islands under this new rule?

hard

A. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to the DFS calls in addition to the four cardinal directions.

B. Keep the DFS calls unchanged but count diagonally adjacent '1's separately after DFS completes.

C. Use BFS instead of DFS without changing neighbor directions, as BFS handles diagonal connectivity automatically.

D. Modify the grid to mark diagonal neighbors as '1' before running the original DFS.

Solution

1. Step 1: Understand the new connectivity rule

   Islands now connect horizontally, vertically, and diagonally, so DFS must explore all 8 neighbors.

2. Step 2: Modify DFS to include diagonal neighbors

   Add recursive DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), and (r-1,c-1) along with the original four directions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only adding diagonal neighbors to DFS ensures correct island counting with 8-direction connectivity [OK]

Hint: Add diagonal neighbors to DFS for 8-direction connectivity [OK]

Common Mistakes:

• Assuming BFS handles diagonals without code change
• Counting diagonals separately after DFS