743. Network Delay Time

At a Glance

Topic: graphs
Pattern: Dijkstra shortest path (BFS family / weighted routing)
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Uber, Bloomberg
Frequency: High
LeetCode: 743

Problem (one-liner)

Directed weighted edges (source, target, time). Signal starts at node k. Return time until all nodes receive signal, or -1 if unreachable.

Recognition Cues

Non-negative weights — Dijkstra
Need maximum among shortest-path distances from source — broadcast completion time

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Bellman-Ford — works but slower — O(VE).
Optimal — Dijkstra with min-heap — O((V+E) log V).

Optimal Solution

Go

import (
	"container/heap"
)

type edge struct {
	target int
	weight int
}

type heapNode struct {
	node     int
	distance int
}

type distanceHeap []heapNode

func (heapSlice distanceHeap) Len() int { return len(heapSlice) }
func (heapSlice distanceHeap) Less(left, right int) bool {
	return heapSlice[left].distance < heapSlice[right].distance
}
func (heapSlice distanceHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *distanceHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(heapNode))
}

func (heapSlice *distanceHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	item := old[length-1]
	*heapSlice = old[0 : length-1]
	return item
}

func networkDelayTime(times [][]int, nodeCount int, source int) int {
	graph := make(map[int][]edge)
	for _, row := range times {
		from := row[0]
		to := row[1]
		weight := row[2]
		graph[from] = append(graph[from], edge{target: to, weight: weight})
	}
	distances := make([]int, nodeCount+1)
	for index := range distances {
		distances[index] = 1 << 30
	}
	distances[source] = 0
	minHeap := &distanceHeap{}
	heap.Init(minHeap)
	heap.Push(minHeap, heapNode{node: source, distance: 0})
	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(heapNode)
		if current.distance > distances[current.node] {
			continue
		}
		for _, neighbor := range graph[current.node] {
			nextDist := current.distance + neighbor.weight
			if nextDist < distances[neighbor.target] {
				distances[neighbor.target] = nextDist
				heap.Push(minHeap, heapNode{node: neighbor.target, distance: nextDist})
			}
		}
	}
	longest := 0
	for node := 1; node <= nodeCount; node++ {
		if distances[node] > longest {
			longest = distances[node]
		}
	}
	if longest >= 1<<30 {
		return -1
	}
	return longest
}

JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index].distance >= this.data[parentIndex].distance) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let smallest = index;
      if (leftChild < length && this.data[leftChild].distance < this.data[smallest].distance) {
        smallest = leftChild;
      }
      if (rightChild < length && this.data[rightChild].distance < this.data[smallest].distance) {
        smallest = rightChild;
      }
      if (smallest === index) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function networkDelayTime(times, nodeCount, source) {
  const graph = new Map();
  for (const row of times) {
    const [from, to, weight] = row;
    if (!graph.has(from)) {
      graph.set(from, []);
    }
    graph.get(from).push({ target: to, weight });
  }
  const distances = new Array(nodeCount + 1).fill(Number.POSITIVE_INFINITY);
  distances[source] = 0;
  const heap = new MinHeap();
  heap.push({ node: source, distance: 0 });
  while (heap.size() > 0) {
    const current = heap.pop();
    if (current.distance > distances[current.node]) {
      continue;
    }
    const neighbors = graph.get(current.node) ?? [];
    for (const neighbor of neighbors) {
      const nextDistance = current.distance + neighbor.weight;
      if (nextDistance < distances[neighbor.target]) {
        distances[neighbor.target] = nextDistance;
        heap.push({ node: neighbor.target, distance: nextDistance });
      }
    }
  }
  let longest = 0;
  for (let node = 1; node <= nodeCount; node += 1) {
    longest = Math.max(longest, distances[node]);
  }
  return longest === Number.POSITIVE_INFINITY ? -1 : longest;
}