1376.time-needed-to-inform-all-employees.md

1376. Time Needed to Inform All Employees

Traversal

informTime[i] is the time needed for node i to inform all its children.

informTime = 
A: 10
C: 100
D: 5
       A
    /  |  \ 10
   B   C   D
    100|   |5  \5
       E   F    G

A -> B
  10           = 10
A -> C -> E
  10   100     = 110
A -> D -> F/G
  10   5       = 15

We just simulate the process of informing all employees via DFS or BFS.

• Top-down: A -> B means A takes 10 minutes to inform B.
• Bottom-up: A <- B means total time is 10 + dfs(B).

• Top-down: 把 A 的時間往下帶到 B。
• Bottom-up: 把子樹的時間總結後，加上 A 的時間往上傳。

           A
     /  |  |  |  \
    B   C  D  E   F

// Top-down
dfs(A) = maxOf(
    dfs(B, informTime[A]),
    dfs(C, informTime[A]),
    ...
)

// Bottom-up
dfs(A) = informTime[A] + max(dfs(B), dfs(C), dfs(D), dfs(E), dfs(F))

private var answer = 0

fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
    val graph = buildGraph(n, manager)
    // dfs(graph, headID, informTime, 0)
    // return answer
    return bfs(graph, headID, informTime)
}

// Top-down without return value, we pass the current inform time in top-down manner
private fun dfs(graph: Array<HashSet<Int>>, i: Int, informTimes: IntArray, currentInformTime: Int) {
    val newTime = currentInformTime + informTimes[i]
    answer = maxOf(answer, newTime)
    graph[i].forEach { adj ->
        dfs(graph, adj, informTimes, newTime)
    }
}

// Bottom-up with return value
private fun dfs(graph: Array<HashSet<Int>>, i: Int, informTime: IntArray): Int {
    var time = 0
    graph[i].forEach { adj -> 
        time = maxOf(time, dfs(graph, adj, informTime))
    }
    return informTime[i] + time
}


// Top-down BFS, we enqueue the node with its inform time
private fun bfs(graph: Array<HashSet<Int>>, headID: Int, informTimes: IntArray): Int {
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(headID to informTimes[headID])
    var answer = 0
    while (queue.isNotEmpty()) {
        val (employee, time) = queue.removeFirst()
        answer = maxOf(answer, time)
        graph[employee].forEach { adj ->
            queue.addLast(adj to time + informTimes[adj])
        }
    }
    return answer
}

private fun buildGraph(n: Int, manager: IntArray): Array<HashSet<Int>> {
    val graph = Array(n) { HashSet<Int>() }
    for (i in manager.indices) {
        if (manager[i] == -1) continue
        graph[manager[i]].add(i)
    }
    return graph
}

• Time Complexity: O(N), each node is visited once, regardless of the number of its children.
  • When iterating over the adjacency list graph[i].forEach { adj -> ... }, we just visit each adjacent node once and each adjacent node is visited once. It doesn't multiply the time complexity.
  • Total work is bounded by the number of edge: In a tree with n nodes, there are exactly n - 1 edges. (See below)
• Space Complexity: O(N), recursive stack depth + adjacency list.

Complexity Explanations

          A
     /  |   |  \
    B   C   D   E
   /    |        \
  F     G         H

DFS traversal:
Visit `A` → iterate through [B, C, D, E] (4 iterations)
    Visit `B` → iterate through [F] (1 iteration)
        Visit `F` → no children (0 iterations)
    Visit `C` → iterate through [G] (1 iteration)
        Visit `G` → no children (0 iterations)
    Visit `D` → no children (0 iterations)
    Visit `E` → iterate through [H] (1 iteration)
        Visit H → no children (0 iterations)

Total iterations in forEach loops: 4 + 1 + 0 + 1 + 0 + 0 + 1 + 0 = 7

But notice: 7 = N-1 = 8-1, which is exactly the number of edges in the tree! The forEach loop might look like it could cause O(N^2) complexity if you think "for each node, we might iterate through all other nodes," but that's not what happens because each node and edge is visited once.

Proof:

• Nodes: n
• Edges: n - 1
• The time complexity of graph is O(V + E), which is O(n + n - 1) = O(n).

My Original Implementation (WA)

I solved this problem by level by level BFS.

        head
     /  |  |  \      (5)
    m1  m2 m3  m4
   /    |  |    \    max(1, 2, 3, 4)
  e1   e2  e3   e4
    \      |
     e5    e6        max(3, 5)

The level by level BFS failed at the case:

        head
     /  |  |  \      (5)
    m1  m2 m3  m4
   /    |  |    \    max(1, 20, 3, 4)
  e1    |  e3   e4
    \   |  |
     e5 |  e6        max(3, 5) = 5
        |
        |
        |
        e2

// Level by level BFS (WA)
max(1, 20, 3, 4) + max(3, 5) = 20 + 5 = 25

// Correct
e1 + e5 = 1 + 3 = 4
e2 = 20
e3 + e6 = 3 + 5 = 8
e4 = 4

max(4, 20, 8, 4) = 20

That e2 is long enough to cover e1 + e5, e3 + e6, e4, which breaks the level by level BFS.

fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
    val graph = buildGraph(n, manager)
    var minutes = 0
    val queue = ArrayDeque<Int>()
    queue.addLast(headID)
    while (queue.isNotEmpty()) {
        val size = queue.size
        var maxTime = 0
        repeat (size) {
            val node = queue.removeFirst()
            val time = informTime[node]
            if (graph[node].isNotEmpty()) {
                maxTime = maxOf(maxTime, time)
            }
            graph[node].forEach { adj -> 
                queue.addLast(adj)
            }
        }
        minutes += maxTime
    }
    return minutes
}