# 03.06.2023 [1376. Time Needed to Inform All Employees]

03.06.2023

1376. Time Needed to Inform All Employees medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/234

Problem TLDR

Total time from headID to all nodes in graph.

Intuition

Total time will be the maximum time from the root of the graph to the lowest node. To find it out, we can use DFS.

Approach

Build the graph, then write the DFS.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(n)

Code

fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
    val fromTo = mutableMapOf<Int, MutableList<Int>>()
        (0 until n).forEach { fromTo.getOrPut(manager[it]) { mutableListOf() } += it }
        fun dfs(curr: Int): Int {
            return informTime[curr] + (fromTo[curr]?.map { dfs(it) }?.max() ?: 0)
        }
        return dfs(headID)
    }