Network Delay Time - Practice Coding Problems

Network Delay Time - Problem

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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 minimum 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.

Input & Output

Example 1 — Basic Network

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

› Output: 2

💡 Note: From node 2: reaches node 1 in time 1, node 3 in time 1, and node 4 in time 2. All nodes receive the signal by time 2.

Example 2 — Unreachable Node

$ Input: times = [[1,2,1]], n = 2, k = 2

› Output: -1

💡 Note: Starting from node 2, we cannot reach node 1 (edge only goes from 1→2). Return -1.

Example 3 — Single Node

$ Input: times = [], n = 1, k = 1

› Output: 0

💡 Note: Only one node exists and it's the source. Signal reaches immediately at time 0.

Constraints

1 ≤ k ≤ n ≤ 100
1 ≤ times.length ≤ 6000
times[i].length == 3
1 ≤ u_i, v_i ≤ n
u_i ≠ v_i
0 ≤ w_i ≤ 100
All the pairs (u_i, v_i) are unique

Visualization

Tap to expand

Understanding the Visualization

Input Network

Directed graph with weighted edges and source node

Signal Propagation

Signal travels along shortest paths to all reachable nodes

Final Result

Time when the last node receives the signal

Key Takeaway

🎯 Key Insight: The network delay is the maximum shortest path distance from source to any node

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to find the longest shortest path from source to any node. Dijkstra's algorithm efficiently computes shortest paths, and the maximum distance represents when the last node receives the signal. Time: O((V + E) × log V), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ Dijkstra's Algorithm	O((V + E) × log V)	O(V + E)	Use Dijkstra's shortest path algorithm with priority queue
Brute Force - DFS All Paths	O(n × 2^n)	O(n)	Explore all possible paths to find minimum time to each node

Dijkstra's Algorithm — Algorithm Steps

Build adjacency list from edges
Use priority queue to process nodes by minimum distance
Update distances and track maximum time
Return max distance or -1 if unreachable nodes exist

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set source distance to 0, others to infinity

Process Queue

Always process node with minimum distance

Update Neighbors

Relax edges and update distances

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_NODES 101
#define MAX_EDGES 1000
#define MAX_HEAP 10000

typedef struct {
    int to;
    int weight;
} Edge;

typedef struct {
    int dist;
    int node;
} HeapNode;

Edge graph[MAX_NODES][MAX_EDGES];
int graphSize[MAX_NODES];
int distances[MAX_NODES];
HeapNode heap[MAX_HEAP];
int heapSize;

void heapPush(int dist, int node) {
    heap[heapSize].dist = dist;
    heap[heapSize].node = node;
    
    int i = heapSize;
    while (i > 0 && heap[i].dist < heap[(i - 1) / 2].dist) {
        HeapNode temp = heap[i];
        heap[i] = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
    heapSize++;
}

HeapNode heapPop() {
    HeapNode min = heap[0];
    heap[0] = heap[--heapSize];
    
    int i = 0;
    while (1) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < heapSize && heap[left].dist < heap[smallest].dist) {
            smallest = left;
        }
        if (right < heapSize && heap[right].dist < heap[smallest].dist) {
            smallest = right;
        }
        
        if (smallest == i) break;
        
        HeapNode temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        i = smallest;
    }
    
    return min;
}

int solution(int times[][3], int timesSize, int n, int k) {
    // Initialize
    memset(graphSize, 0, sizeof(graphSize));
    heapSize = 0;
    
    // Build adjacency list
    for (int i = 0; i < timesSize; i++) {
        int u = times[i][0];
        int v = times[i][1];
        int w = times[i][2];
        
        graph[u][graphSize[u]].to = v;
        graph[u][graphSize[u]].weight = w;
        graphSize[u]++;
    }
    
    // Initialize distances
    for (int i = 1; i <= n; i++) {
        distances[i] = INT_MAX;
    }
    distances[k] = 0;
    
    // Dijkstra's algorithm
    heapPush(0, k);
    
    while (heapSize > 0) {
        HeapNode current = heapPop();
        int currentDist = current.dist;
        int node = current.node;
        
        if (currentDist > distances[node]) {
            continue;
        }
        
        for (int i = 0; i < graphSize[node]; i++) {
            Edge edge = graph[node][i];
            int neighbor = edge.to;
            int weight = edge.weight;
            int newDist = currentDist + weight;
            
            if (newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                heapPush(newDist, neighbor);
            }
        }
    }
    
    // Find maximum distance
    int maxTime = 0;
    for (int i = 1; i <= n; i++) {
        if (distances[i] == INT_MAX) {
            return -1;
        }
        if (distances[i] > maxTime) {
            maxTime = distances[i];
        }
    }
    
    return maxTime;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse times array
    int times[MAX_EDGES][3];
    int timesSize = 0;
    
    char* ptr = line;
    while (*ptr && timesSize < MAX_EDGES) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            sscanf(ptr, "[%d,%d,%d]", &times[timesSize][0], &times[timesSize][1], &times[timesSize][2]);
            timesSize++;
        }
        ptr++;
    }
    
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    printf("%d\n", solution(times, timesSize, n, k));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((V + E) × log V)

Each edge relaxation takes O(log V) due to priority queue operations

⚡ Linearithmic

Space Complexity

O(V + E)

Adjacency list storage and priority queue space

✓ Linear Space

185.0K Views

Medium Frequency

~25 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dijkstra's Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler